#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;
}

• Re:...这个代码不像并查集吧.... (0) zhishicece 2012-02-19 20:40:27