POJ 2513 Colored Sticks (Trie树,欧拉通路,并查集)

  • Post author:
  • Post category:其他


Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

Hint

Huge input,scanf is recommended.


每根木棒两端都有一种颜色,如果两根木棒一端有相同的颜色,则可以连在一块。给出一系列木棒的颜色,问这些木棒可不可以连成一条直线。


思想为建图,一种颜色为一个节点,不同的木棒相同的颜色是一个节点,如果能连成一条直线的话,那么所建的图一定是连通图,且从起点出发,每条边只能经过一次(直线就是这样),这就想到了欧拉通路。


欧拉通路———通过图中每条边一次且仅一次,并且经过每一顶点的通路。


对于无向图来说:


G有欧拉通路的充分必要条件为:G 连通,G中只有两个奇度顶点(它们分别是欧拉通路的起点和终点)。


所以我们要解决两个问题:


1.怎样判断建的图是连通的?


2.怎样判断奇度顶点的个数?


对于第一个问题,采用并查集可以解决,只要所有的顶点都在一个集合里面,那么图一定是连通的,这又衍生出一个问题,使用并查集的时候,得需要节点的编号才可以,怎样确定节点的编号呢?可以采用trie树来确定节点的编号,cnt=1,按照颜色字符串输入的顺序,在trie树中建立一条路径,只要发现以前没有过该字符串,就让其id=cnt++,那么所输入的颜色节点的编号就变为了 1— cnt-1


对于第二个问题,用degree[]数组来保存每个顶点的度。无向图中,一个顶点的度就是有多少条边与其相连,所以在输入的时候,对于输入的两种颜色,对其编号进行degree[编号] ++就可以了。上面所说的奇度顶点(欧拉通路的两个端点),欧拉通路的两个端点有两种情况,一是颜色相同,那么在我们所建立的图上这两个端点是重合的,也就是奇度顶点的个数为0,另一种情况,颜色不同,那么奇度顶点就为2了,所以我们在这里要判断的是奇度顶点是否等于0或者等于2.

#include <iostream>

#include <string.h>

#include <stdio.h>

using namespace std;

#define maxn 250000

int degree[maxn*2+1],parent[maxn*2+1];//每个节点的度和根节点

int cnt=1;//顶点个数

struct Trie

{

bool ok;

int id;

Trie *next[27];

Trie()

{

ok=0;

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

next[i]=NULL;

}

}root;

int Hash(char *s)

{

int len=strlen(s);

Trie *p=&root;

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

{

int id=s[i]-‘a’;

if(p->next[id]==NULL)

p->next[id]=new Trie();

p=p->next[id];

}

if(p->ok==1)return p->id;

else

{

p->ok=1;

p->id=cnt++;

}

return p->id;

}

int find(int x)

{

if(parent[x]==x)return x;

else return parent[x]=find(parent[x]);

}

void Union(int x,int y)

{

x=find(x);

y=find(y);

if(x==y)return;

else parent[x]=y;

}

int main()

{

char s1[11],s2[11];

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

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

parent[i]=i;

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

{

int x=Hash(s1),y=Hash(s2);

degree[x]++;degree[y]++;

Union(x,y);

}

cnt–;

int self=0,oddnum=0;//根节点个数,度数为奇数的个数

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

{

if(degree[i]%2==1)

oddnum++;

if(parent[i]==i)

self++;

if(self>=2||oddnum>=3)

{

cout<<“Impossible”<<endl;

return 0;

}

}

if(oddnum==0||oddnum==2)

cout<<“Possible”<<endl;

return 0;

}

转载于:https://www.cnblogs.com/MisdomTianYa/p/6581699.html