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大学生程序设计竞赛训练》暑期课面向全球招生!

Re:怎麼我的并查集這組數據輸出不是樹 附代碼

Posted by 1100012760 at 2012-08-01 22:13:55 on Problem 1308
In Reply To:Re:同志们:利用并查集是错的,我用并查集也AC了,但是仔细研究后,发现是错了,数据太弱了 Posted by:tangcong506 at 2011-10-30 18:25:00
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
int key[10001] , indegree[10001] , t;
int fun(int a)
{
	if(key[a]==a) return a;
	key[a] = fun(key[a]);
	return key[a];
}
int main()
{
	int casenum = 0 , a , b , p1 , p2 , i , c , d , f , root;
	map<int,int> v;
	bool flag , end = false;
	while(1)
	{
		casenum++;
		flag = true;
		v.clear();
		t = root = 0;
		memset(indegree,0,sizeof(indegree));
		while(cin>>a>>b)
		{
			if(a==0)
				break;
			if(a==-1)
			{
				end = true;
				break;
			}
			if(v.count(a)==0)
			{
				t++;
				v.insert(make_pair(a,t));
				p1 = t;
				key[p1] = p1;
			}
			else
				p1 = v[a];
			if(v.count(b)==0)
			{
				t++;
				v.insert(make_pair(b,t));
				p2 = t;
				key[p2] = p2;
			}
			else
				p2 = v[b];
			indegree[p2]++;
			c = fun(p1);
			d = fun(p2);
			if(c!=d) key[c] = d;
		}
		if(end) break;
		f = fun(1);
		for(i = 1 ; i <= t ; i++)
			if(fun(i)!=f)
				flag = false;
		for(i = 1 ; i <= t ; i++)
		{
			if(indegree[i]>1)
				flag = false;	
			if(indegree[i]==0)
				root++;
		}
		if(root!=1) flag = false;
		if(t==0) flag = true;
		if(flag) cout << "Case " << casenum <<  " is a tree." << endl;
		else 	cout << "Case " << casenum <<  " is not a tree." << endl;
	}
	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