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

根本不需要用并查集来判断森林!

Posted by w446506278 at 2016-01-13 15:14:08 on Problem 1308
只要判断下建好的树的根有几个就可以了~
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int MAX=100005;
int pre[MAX];
bool vis[MAX];
bool flag;

int main()
{
	int u,v,cas=1;
	while(~scanf("%d%d",&u,&v)&&(u!=-1||v!=-1))
	{
		if(u==0&&v==0)
		{
			printf("Case %d is a tree.\n",cas++);
			continue;
		}
		memset(pre,-1,sizeof(pre));
		queue<int> q;
		flag=true;
		if(u==v)
		{
			flag=false;
		}
		else
		{
			pre[v]=u;
			q.push(v);
			q.push(u);
		}
		while(scanf("%d%d",&u,&v)&&(u!=0||v!=0))
		{
			if(flag==false) continue;
			if(pre[v]!=-1)
			{
				flag=false;
				continue;
			}
			else if(u==v)
			{
				flag=false;
				continue;
			}
			else if(pre[u]==v)
			{
				flag=false;
				continue;
			}
			else
			{
				pre[v]=u;
		    	q.push(v);
	    		q.push(u);
			}
		}
		if(flag==true)//判断森林
		{
			int num=0;
			memset(vis,false,sizeof(vis));
			while(!q.empty())
			{
				v=q.front();
				q.pop();
				if(vis[v]==true) continue;
				vis[v]=true;
				if(pre[v]==-1)
				{
					num++;
				}
			}
			if(num!=1) flag=false;//判断根个数
		}
		if(flag) printf("Case %d is a tree.\n",cas++);
		else printf("Case %d is not a tree.\n",cas++);
	}
	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