PAT (Advanced Level) 1021. Deepest Root (25)

先并查集判断连通性,然后暴力每个点作为根节点判即可。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std; struct Edge
{
int a,b;
}e[];
int n,sz,f[],dep,U;
bool flag[];
vector<int>g[]; int Find(int x)
{
if(x!=f[x]) return f[x]=Find(f[x]);
return f[x];
} void dfs(int x,int d)
{
dep=max(dep,d); flag[x]=;
for(int i=;i<g[x].size();i++)
if(flag[g[x][i]]==) dfs(g[x][i],d+);
} void DFS(int x,int d)
{
U=max(U,d); flag[x]=;
for(int i=;i<g[x].size();i++)
if(flag[g[x][i]]==) DFS(g[x][i],d+);
} int main()
{
scanf("%d",&n); sz=n;
for(int i=;i<=n;i++) {g[i].clear();f[i]=i;}
for(int i=;i<=n-;i++)
{
scanf("%d%d",&e[i].a,&e[i].b);
g[e[i].a].push_back(e[i].b);
g[e[i].b].push_back(e[i].a);
}
for(int i=;i<=n-;i++)
{
int fx=Find(e[i].a), fy=Find(e[i].b);
if(fx!=fy) { sz--; f[fx]=fy; }
}
if(sz!=) printf("Error: %d components\n",sz);
else
{
dep=;
for(int i=;i<=n;i++)
{
memset(flag,,sizeof flag);
dfs(i,);
} for(int i=;i<=n;i++)
{
U=;
memset(flag,,sizeof flag);
DFS(i,);
if(U==dep) printf("%d\n",i);
}
}
return ;
}
上一篇:jQuery(function($){...})与(function($){...})(jQuery)知识点分享


下一篇:c构造函数