题目传送门

题目大意：给你一堆木棍，每根木管都有两种颜色，相同颜色的部分可以连接起来，问你这堆木棍可不可以连接成1根。

思路：大致的思路很好想，就是判断欧拉回路的方法（1.联通，2，要么顶点读书全为偶数，要么有两个奇数），统计每种颜色出现的次数就可以了。问题的关键是怎么统计，大家第一反应肯定是并查集统计联通路，用map统计次数，但这道题的数据量是25w*2，map会超时，然后想到了字典树。

我是用数组写的字典树，root表示的是某一种颜色的标号，（哈希的思想），这样空间开的会很大，理论上应该过不了，但是A了。

还有一种方法是链表写字典树，这也是我第一次用链表写题目，借鉴了kuangbin老师的博客，接下来两种代码都附上。

//数组写法  好理解

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<bitset>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

using namespace std;

typedef pair<int,int> pii;

typedef long long ll;

const double PI=acos(-1.0);

int fact[10]= {1,1,2,6,24,120,720,5040,40320,362880};

const int maxn= 5000010;

int in[maxn],ou[maxn];

int tot;

int trie[maxn][26];// 最多50w个单词  开50w*10 （居然没爆 md）

int fa[maxn];

int find(int x){

	return x==fa[x]?x:fa[x]=find(fa[x]);

}

void baba(int x,int y){

	int fx=find(x),fy=find(y);

	fa[fx]=fy;

}

int iinsert(char *s)

{

	int root=0;

	int len=strlen(s);

	for(int i=0;i<len;i++)

	{

		int id=s[i]-'a';

		if(!trie[root][id])

		{

			trie[root][id]=++tot;

		}

		root=trie[root][id];

	}

	return root;//root表示某一个字母的标号  虽然数字分布的很宽   不过空间换时间

}

bool v[maxn];

int main(){

	char s1[20],s2[20];

	int x,y;

	int cas=0;

	memset(v,false,sizeof(v));

	for(int i=1;i<=maxn;i++)fa[i]=i;

	while(scanf("%s%s",s1,s2)!=EOF)

	{

		x=iinsert(s1);

		y=iinsert(s2);

		in[x]++;//统计出度  和  入度  欧拉回路判定标准

		ou[y]++;

		baba(x,y);//将可以连着的木棍并查集并起来  防止出现两个欧拉回路

		v[x]=true;//由于之前的root分布的太广了  所以用v[]来表示某一个数字是否代表了一种颜色  不是的话就直接跳过  节约时间

		v[y]=true;

	}

	int f1=0,m=-1,flag=0;

	for(int i=1;i<=tot;i++)

	{

		if(v[i])

		if(find(i)!=m){

			if(!flag){

				m=find(i);

				flag=1;

			}else{//如果连通图超过两个就不对了

				printf("Impossible\n");

				return 0;

			}

		}

		if(!v[i]||in[i]==ou[i])continue;

		if((in[i]+ou[i])%2)

		{

			f1++;

		}

		if(f1>2)//如果奇数点超过两个就不对了

		{

			printf("Impossible\n");

			return 0;

		}

	}

	printf("Possible\n");

}

//链表写法

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<bitset>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

using namespace std;

typedef long long ll;

const int maxn=500010;

int color;

int fa[maxn];

int degree[maxn];

int find(int x)

{

	return  fa[x]==x?x:fa[x]=find(fa[x]);

}

void baba(int x,int y)

{

	int fx=find(x),fy=find(y);

	fa[fx]=fy;

}

const int MAX=26;

typedef struct trie_node

{

	bool isword;

	struct trie_node *next[MAX];//链表

	int id;

}trie;

int insert(trie *root,char *s)

{

	trie *p=root;

	int i=0;

	while(s[i]!='\0')

	{

		if(p->next[s[i]-'a']==NULL)

		{

			trie *temp=new trie;

			temp->isword=false;//如果没有这个节点，则标记为没有访问过

			for(int j=0;j<MAX;j++)

			{

				temp->next[j]=NULL;//将新节点的每一个子节点都赋值为NULL

			}

			temp->id=0;

			p->next[s[i]-'a']=temp;

		}

		p=p->next[s[i]-'a'];//顺着字典树走

		i++;

	}

	if(p->isword)//如果访问过（之前插入过  id应该已经有值了）

	{

		return p->id;

	}

	else

	{

		p->isword=true;//如果没有  说明是新的颜色

		p->id=color++;

		return p->id;

	}

}

int main(){

	char s1[20],s2[20];

	trie *root=new trie;

	for(int i=0;i<26;i++)

		root->next[i]=NULL;

	root->isword=false;

	root->id=0;

	color=0;

	for(int i=0;i<maxn;i++)fa[i]=i;

	memset(degree,0,sizeof(degree));

	while(scanf("%s%s",&s1,&s2)!=EOF)

	{

		int t1=insert(root,s1);

		int t2=insert(root,s2);

		degree[t1]++;

		degree[t2]++;

		baba(t1,t2);

	}

	int cnt1=0,cnt2=0;

    for(int i=0;i<color;i++)

    {

        if(fa[i]==i)cnt1++;

        if(degree[i]%2==1)cnt2++;

        if(cnt1>1)break;

        if(cnt2>2)break;

    }

    if((cnt1==0||cnt1==1)&&(cnt2==0||cnt2==2))

      printf("Possible\n");

    else printf("Impossible\n");

    return 0;

} 

Description

Input

Output

Sample Input

blue red

red violet

cyan blue

blue magenta

magenta cyan

Sample Output

Possible

Hint