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
#include <stdio.h> #include <iostream> using namespace std; int id = 0, par[500010], degree[500010] = {0}; int find_set(int x) { return par[x] != x ? par[x] = find_set(par[x]) : x; } struct Trie_node { int flag, id; struct Trie_node *next[26]; Trie_node() { for(int i = 0; i < 26; i++) next[i] = NULL; flag = 0; } }; int trie_insert(struct Trie_node *p, char s[]) { for(int i = 0; s[i]; i++) { if(p->next[s[i]-'a'] == NULL) p->next[s[i]-'a'] = new Trie_node; p = p->next[s[i]-'a']; } if(p->flag != 1) { p->flag = 1; p->id = ++id; } return p->id; } bool check() { int x = find_set(1); for(int i = 2; i <= id; i++) { if(find_set(i) != x) return 0; } int degree_odd = 0; for(int i = 1; i <= id; i++) { if(degree[i] & 1) degree_odd++; } return (degree_odd == 1 || degree_odd > 2) ? 0 : 1; } int main() { for(int i = 0; i <= 500000; i++) par[i] = i; struct Trie_node *root = new Trie_node; char s1[12], s2[12]; while(scanf("%s %s", s1, s2) != EOF) { int x = trie_insert(root, s1); int y = trie_insert(root, s2); degree[x]++; degree[y]++; int fx = find_set(x); int fy = find_set(y); if(fx != fy) par[fx] = fy; } printf("%s ", check() ? "Possible" : "Impossible"); return 0; }