Colored Sticks
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
题目类型：无向图欧拉回路(路径)的判定
算法分析：将颜色看成节点，连接颜色的木棒看成一条无向边。使用并查集判断构建的图中是否连通，然后统计每一个节点的奇数度数的个数，直接使用欧拉路径和回路的判断定理判断即可。注意需要使用trie树或者是hash表进行字符串的快速检索和插入，直接使用O(n)的算法会超时。注意数据中可能出现自环，即代码中的id可能最小取值到0，所以在判断连通性时下标需要从0开始！！！下面会给出使用Trie树实现的代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const int maxn = 500000 + 666; int len = 0; char ans[maxn][16],val_a[16], val_b[16]; int parent[maxn], deg[maxn]; struct Node { int id; char s[16]; }; vector <Node> vec[maxn]; unsigned int BKDRHash (char *val) { unsigned int seed = 131, hash_val = 0; while (*val) { hash_val = hash_val * seed + (*val++); } return hash_val % maxn; } int Get (char *val) { int key = BKDRHash (val), i; for (i = 0; i < vec[key].size (); i++) if (!strcmp (val, vec[key][i].s)) return vec[key][i].id; Node temp; strcpy (temp.s, val); temp.id = len++; vec[key].push_back (temp); return temp.id; } int UnFind (int val) { if (parent[val] == val) return val; return parent[val] = UnFind (parent[val]); } int main() { // freopen ("aaa.txt", "r", stdin); memset (deg, 0, sizeof (deg)); int i; for (i = 0; i < maxn; i++) parent[i] = i; while (scanf ("%s%s", val_a, val_b) != EOF) { int u = Get (val_a); int v = Get (val_b); deg[u]++; deg[v]++; if (UnFind (u) != UnFind (v)) parent[UnFind(u)] = UnFind (v); } int odd = 0; for (i = 0; i < len; i++) { if (deg[i] % 2) odd++; } bool is_valid = true; int temp = UnFind (0); for (i = 0; i < len; i++) if (temp != UnFind (i)) { is_valid = false; break; } if ((odd == 0 || odd == 2) && is_valid) printf ("Possible\n"); else printf ("Impossible\n"); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 |
//注意数据中可能出现自环，即代码中的id可能最小取值到0，所以在判断连通性时下标需要从0开始！！！ #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 26; const int nodemaxn = 500000 + 66; int id, aacnt[nodemaxn], parent[nodemaxn]; struct Trie { int Next[nodemaxn][maxn], last[nodemaxn]; int len, root; int newnode () { for (int i = 0; i < maxn;i++) Next[len][i] = -1; last[len] = -1; len++; return len - 1; } void Init () { len = 0; root = newnode (); } void Insert (char *s, int vv) { int p = root; for (int i = 0; s[i]; i++) { if (Next[p][s[i]-'a'] == -1) Next[p][s[i]-'a'] = newnode (); p = Next[p][s[i]-'a']; } last[p] = vv; } int Query (char *s) { // cout << s << endl; int p = root; for (int i = 0; s[i]; i++) { if (Next[p][s[i]-'a'] == -1) return -1; p = Next[p][s[i]-'a']; } if (last[p] != -1) return last[p]; return -1; } }; Trie aa; int UnFind (int val) { if (parent[val] == val) return val; return parent[val] = UnFind (parent[val]); } int main() { // ifstream cin("aaa.txt"); // freopen ("aaa.txt", "r", stdin); char sa[66], sb[66]; aa.Init (); id = 0; memset (aacnt, 0, sizeof (aacnt)); for (int i = 0; i < nodemaxn; i++) parent[i] = i; int pp, va, vb; while (scanf ("%s%s", sa, sb) != EOF) { pp = aa.Query (sa); if (pp == -1) { aa.Insert (sa, id); aacnt[id]++; va = id; id++; } else { aacnt[pp]++; va = pp; } pp = aa.Query(sb); if (pp == -1) { aa.Insert (sb, id); aacnt[id]++; vb = id; id++; } else { aacnt[pp]++; vb = pp; } if (UnFind (va) != UnFind (vb)) parent[UnFind(va)] = UnFind (vb); } // for (int i = 0; i < id; i++) // cout << aacnt[i] << endl; int odd = 0; for (int i = 0; i < id; i++) if (aacnt[i] & 1) odd++; bool is_valid = true; int tt = UnFind (0); for (int i = 0; i < id; i++) if (UnFind (i) != tt) { is_valid = false; break; } if ((odd == 0 || odd == 2) && is_valid) puts ("Possible"); else puts ("Impossible"); return 0; } |
- « 上一篇：poj2480
- poj2528：下一篇 »