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

有限图判欧拉回路—coken

Posted by 1340502116 at 2016-07-08 17:41:34 on Problem 1386
#include <iostream>
#include <string.h>
#include <set>
using namespace std;
const int MAXN=30;
char buf[1005];
set<int> vec;
int n;
int par[MAXN],indeg[MAXN],outdeg[MAXN];
void prep()
{
	for(int i=0;i<MAXN;i++)
	{
		par[i]=i;
	}
}
int fnd(int x)
{
	if(par[x]==x)
	{
		return x;
	}
	return par[x]=fnd(par[x]);
}
void unite(int x,int y)
{
	int a=fnd(x);
	int b=fnd(y);
	par[b]=a;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		vec.clear();
		prep();
		memset(indeg,0,sizeof(indeg));
		memset(outdeg,0,sizeof(outdeg));
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>buf;
			int len=strlen(buf);
			int u=buf[0]-'a';
			int v=buf[len-1]-'a';
			unite(u,v);
			vec.insert(u);
			vec.insert(v);
			outdeg[u]++;
			indeg[v]++;
		}	
		int root=-1;
		int s=0;
		int c1=0,c2=0,c3=0;
		for(set<int>:: iterator it=vec.begin();it!=vec.end();it++)
		{
			int rt=fnd(*it);
			if(root!=rt)
			{
				root=rt;		
				s++;
			}
			if(outdeg[*it]-indeg[*it]==1)
			{
				c1++;
			}
			else if(outdeg[*it]==indeg[*it])
			{
				c2++;
			}
			else if(indeg[*it]-outdeg[*it]==1)
			{
				c3++;
			}
			else	;
		}
		if(s==1)
		{
			if((c1==1&&c3==1&&c2==vec.size()-2)||(c1==0&&c3==0&&c2==vec.size()))
			{
				cout<<"Ordering is possible."<<endl;
			}
			else	cout<<"The door cannot be opened."<<endl;
		}
		else
		{
			cout<<"The door cannot be opened."<<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