OI-Wiki 图论相关概念,大概看看眼熟每个词的含义即可。
暂时只需要了解下面说的,还有一个链式前向星回头咱再补充。
int e[MAXM][2]; //e[i][0] -> e[i][1] 是一条边
bool g[MAXN+5][MAXN+5]; //g[i][j]:存 i 点与 j 点的连接关系
vector<int> e[MAXN+5]; //e[i]:存 i 点所有出边的对应点
int e[MAXM][3]; //e[i][0] -> e[i][1] 是一条边,权值为 e[i][2]
int g[MAXN+5][MAXN+5]; //g[i][j]:存 i 点与 j 点这条边的权值(没有边就设置一个特殊值)
struct Edge {
int v, w;
};
vector<Edge> e[MAXN+5];
//e[u]:存 u 点所有出边;
//e[u][i].v:第i条边对应的点;
//e[u][i].w:第 i 条边的权值;
int root; //根节点编号
int ls[105]; //i 号节点的左孩子编号
int rs[105]; //i 号节点的右孩子编号
int n;
vector<int> e[1005];
int dep[1005]; //节点深度
int siz[1005]; //子树大小
// 当前子树根节点,当前子树根节点的父节点
void dfs(int u, int fa)
{
siz[u] = 1;
// 枚举所有u能连到的点v
for (int i = 0; i < e[u].size(); i++)
{
int v = e[u][i];
if (v == fa)
continue; // 忽略父节点方向
dep[v] = dep[u] + 1;
dfs(v, u);
siz[u] += siz[v];
}
}
随便挑一个点 ,距离该点最远的就是直径的一个端点 ,从 找到距离 最远的就是另一个端点
以 为根时相当于把当前除了子树 之外的部分作为了一个新的子树。