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:同志们:利用并查集是错的,我用并查集也AC了,但是仔细研究后,发现是错了,数据太弱了

Posted by Ruby931031 at 2012-03-23 00:20:30 on Problem 1308 and last updated at 2012-03-23 10:47:26
In Reply To:Re:同志们:利用并查集是错的,我用并查集也AC了,但是仔细研究后,发现是错了,数据太弱了 Posted by:tangcong506 at 2011-10-30 18:25:00
我觉得并查集没问题,要看并查集怎么写了!试了一下,我这个代码跑那个数据就没问题。
我可耻的贴代码了:(大牛们不要鄙视我……)

//并查集判连通 + 树的性质(E=V-1)
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 1005
int main()
{
	int i,edge,top=0,x,y,node[MAXN],fa[MAXN];	//top为栈node[]的栈顶指针,同时指示集合不同顶点的数目
	int joint=0,cases=1;
	bool visit[MAXN]={0};
	for (i=1;i<MAXN;i++)		fa[i]=i;
	joint=top=edge=0;
	while ( cin >> x >> y )
	{
		if (x==-1)		break;
		if (!x)		
		{
			for (i=0;i<top;i++)
				if ( fa[node[i]]==node[i] )		joint++;
			if (!top)							//空树直接输出
				cout << "Case " << cases++ << " is a tree." << endl;
			else
			{
				if ( joint==1  &&  edge==top-1)	//若集合连通 并且 E=V-1, 则它是一棵树
					cout << "Case " << cases++ << " is a tree." << endl;
				else
					cout << "Case " << cases++ << " is not a tree." << endl;
			}
			joint=edge=top=0;
			for (i=1;i<MAXN;i++)		fa[i]=i;
			memset(visit,false,sizeof(visit));
			continue;
		}
		edge++;
		if ( !visit[x] )
		{visit[x]=true;node[top++]=x;}
		if ( !visit[y] )
		{visit[y]=true;node[top++]=y;}
		fa[y]=x;		//注意这里,我没有写fa[find(y)]=find(x);而是直接把x作为y的父节点
	}
	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