POJ-2513-Colored Sticks

地址：http://poj.org/problem?id=2513

思路：可以用map将所有颜色编号并记录每种颜色的个数，由欧拉回路知，每个颜色个数为奇数的个数>2时就不成立，再利用并查集判断是否在同一个集合即可。

Code :

#include<iostream>
#include<map>
using namespace std;

const int MAX_S=100005; 
string s1,s2;
map<string,int> imap;
int id[MAX_S],Sum[MAX_S];

int Find(int x);
void Union(int a,int b);
int main()
{
	ios::sync_with_stdio(false);
	for(int i=0;i<MAX_S;++i)
		id[i]=i;
	int n=0;
	while(cin>>s1>>s2){
		if(imap[s1]==0)	imap[s1]=++n;
		if(imap[s2]==0)	imap[s2]=++n;
		++Sum[imap[s1]];	++Sum[imap[s2]];
		Union(imap[s1],imap[s2]);
	}
	bool boo=true;
	int t=0;
	int p=Find(id[1]);
	for(int i=1;i<=n;++i)
	{
		if(Find(id[i])!=p){
			boo=false;	break;
		}
		if(Sum[i]%2)	++t;
	}
	if(t>2)	boo=false;
	if(boo==true)	 cout<<"Possible"<<endl;
	else	cout<<"Impossible"<<endl;
	
	return 0;
}

int Find(int x)
{
	if(id[x]!=x)	id[x]=Find(id[x]);
	return id[x];
}

void Union(int a,int b)
{
	id[Find(a)]=Find(b);
}