Time Limit: 5000MS | Memory Limit: 128000K | |
Total Submissions: 37340 | Accepted: 9796 |
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.
Source
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<sstream> #include<algorithm> #include<queue> #include<deque> #include<iomanip> #include<vector> #include<cmath> #include<map> #include<stack> #include<set> #include<fstream> #include<memory> #include<list> #include<string> using namespace std; typedef long long LL; typedef unsigned long long ULL; #define MAXN 500008 #define INF 1000000009 #define eps 0.00000001 /* 欧拉路 一笔画问题! Trie树就是一种节省空间的hash 利用并查集判断是否联通 */ char a[15], b[15]; int cnt = 0, index = 1, pre[MAXN], degree[MAXN]; typedef struct node { bool flag; int id; struct node* next[26]; }*Tree; node memory[MAXN]; Tree Newnode() { Tree T = &memory[cnt++]; T->flag = false; T->id = -1; for (int i = 0; i < 26; i++) T->next[i] = NULL; return T; } int Insert(char* s, Tree T) { int p = 0; while (s[p] != '