Maison > Questions et réponses > le corps du texte
1.pat 1021 deepest root 第4个测试点无法通过
2.代码:跟参考答案代码基本一致,只是变量名变了而已;求大神指出代码中无法通过测试的原因!谢谢
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100010;
vector<int> adj[maxn];
bool root[maxn];
int father[maxn];
void init(int n)
{
for(int i=1;i<=n;++i)
{
father[i]=i;
}
}
int findfather(int x)
{
int a=x;
while(x!=father[x])
{
x=father[x];
}
while(a!=father[a])
{
int temp=a;
a=father[a];
father[temp]=x;
}
return x;
}
void sunion(int a, int b)
{
int fa=father[a];
int fb=father[b];
if(fa!=fb) father[fb]=fa;
}
int blockcount(int n)
{
int block=0;
for(int i=1;i<=n;++i)
{
//int rt=findfather(i);
root[findfather(i)]=true;
}
for(int i=1;i<=n;++i)
{
block+=root[i];
}
return block;
}
int maxheight=0;
vector<int> tempdeepest, ans;
void dfs(int vt, int height, int pre)
{
if(height>maxheight)
{
tempdeepest.clear();
tempdeepest.push_back(vt);
maxheight=height;
}
else if(height==maxheight)
tempdeepest.push_back(vt);
for(int i=0;i<adj[vt].size();++i)
{
//int v=adj[vt][i];
if(adj[vt][i]==pre) continue;
dfs(adj[vt][i], height+1, vt);
}
}
int main()
{
int n;
scanf("%d",&n);
init(n);//忘记了;
int va, vb;
for(int i=1;i<n;++i)//n-1条边;
{
//int va, vb;
scanf("%d%d", &va, &vb);
adj[va].push_back(vb);
adj[vb].push_back(va);
sunion(va, vb);
}
int block=blockcount(n);
if(block!=1)
printf("Error: %d components\n", block);
else
{
dfs(1, 1,-1);
ans=tempdeepest;
dfs(ans[0],1,-1);
for(int i=0;i<tempdeepest.size();++i)
{
//int rt=tempdeepest[i];
ans.push_back(tempdeepest[i]);
}
sort(ans.begin(), ans.end());
printf("%d\n",ans[0]);
for(int i=1;i<ans.size();++i)
{
if(ans[i]!=ans[i-1])
printf("%d\n", ans[i]);
}
}
return 0;
}