P1333 瑞瑞的木棍

题意：给你若干条边，端点是名字，求能否一笔画。图可能不连通。

针对这些名字，显然用一下hash或者trie。

要判断能否一笔画，首先要判断是否只有一个连通块。显然可以用并查集解决。当所有点的fa值相同时就只有一个连通块了。

然后就是一笔画问题的定理：

连通的无向图\(G\)有欧拉路径的充要条件是：\(G\)中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。

连通的无向图\(G\)是欧拉（存在欧拉回路）的充要条件是：\(G\)中每个顶点的度都是偶数。

把奇点大于2的判断一下无解即可。测试点里面没一个奇点的

顺便粘个一笔画问题的第二个定理：（两个定理都来自wikipedia）

如果连通无向图\(G\)有\(2k\)个奇顶点，那么它可以用\(k\)笔画成，并且至少要用\(k\)笔画成。

上面说到的hash就可以使用平板电视里面的两个哈希表之一：

1. cc_hash_table：拉链法hash。
2. gp_hash_table：探测法hash。

个人比较倾向于cc。

代码：

/************************************************************************* @Author: Garen @Created Time : 2019年02月18日 星期一 22时30分55秒 @File Name: P1333.cpp @Description: ************************************************************************/#include
    
     #include
     
      #include
      
       using std::cin;using std::cout;using std::endl;const int maxn = 500005;#define YES puts("Possible")#define NO puts("Impossible")__gnu_pbds::cc_hash_table
       
         hashtable;int fa[maxn];int degree[maxn];int n, m;int find(int x) {    if(fa[x] == x) return x;    return fa[x] = find(fa[x]);}int main() {    std::ios::sync_with_stdio(false);    std::string ch1, ch2;    while(cin >> ch1 >> ch2) {        if(hashtable.find(ch1) == hashtable.end()) {            hashtable[ch1] = ++n; fa[n] = n;        }        if(hashtable.find(ch2) == hashtable.end()) {            hashtable[ch2] = ++n; fa[n] = n;        }        degree[hashtable[ch1]]++; degree[hashtable[ch2]]++;        int u = find(hashtable[ch1]), v = find(hashtable[ch2]);        fa[v] = u;    }    int temp = find(1);    for(int i = 2; i <= n; i++) {        if(find(i) != temp) {            NO; return 0;        }    }    int cnt = 0;    for(int i = 1; i <= n; i++) {        if(degree[i] % 2) cnt++;    }    if(cnt == 1) {        puts("?");        return 0;    }    if(cnt > 2) {        NO; return 0;    }    YES; return 0;}