Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

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

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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator