Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 并查集解决，贴上我的代码，和大家分享

Posted by 200842128 at 2011-11-21 10:03:36 on Problem 1330
```#include<iostream>
#include<set>
#include<string.h>
#include<stdio.h>
using namespace std;

const int Max = 10000 + 10;
int parent[Max];

int getParent(int n)
{
while(parent[n]) n = parent[n];
return n;
}

int main()
{
int cases, nodeNum, a, b, pa, pb;
scanf("%d", &cases);
while(cases--)
{
scanf("%d", &nodeNum);

memset(parent, 0, sizeof(parent));
for(int i=1; i<nodeNum; i++)
{
scanf("%d%d", &a, &b);

pa = getParent(a);
pb = getParent(b);
if(pa != pb) parent[b] = a;
}

scanf("%d%d", &a, &b);
set<int> aAncestor;

aAncestor.insert(a);
while(parent[a])
{
aAncestor.insert(parent[a]);
a = parent[a];
}

if(aAncestor.count(b))
{
cout << b << endl;
}
else
{
while(parent[b])
{
if(aAncestor.count(parent[b]))
{
cout << parent[b] << endl;
break;
}
else
{
b = parent[b];
}
}
}
}

system("pause");
return 0;
}
```

Followed by: