Colored Sticks

问题便转化为：给定一个图，是否存在“一笔画”经过涂中每一点，以及经过每一边一次。这样就是求图中是否存在欧拉路Euler-Path。
由图论知识可以知道，无向图存在欧拉路的充要条件为：
① 图是连通的；
② 所有节点的度为偶数，或者有且只有两个度为奇数的节点。

trie 和并查集

  1 #include <iostream>
  2 #include <vector>
  3 #include <string.h>
  4 #include<stdlib.h>
  5 #include<stdio.h>
  6 using namespace std;
  7 typedef struct trie{
  8     int trie_index;
  9     bool flag;
 10     trie* next[26];
 11 
 12 } Trie;
 13 void trie_init(Trie* tr){
 14     tr->trie_index = -1;
 15     tr->flag = false;
 16     for(int i = 0; i< 26; i ++)
 17         tr->next[i] = NULL;
 18 }
 19 int trie_index;
 20 Trie *root;
 21 vector<int> trie_set;
 22 vector<int> trie_rank;
 23 
 24 int trie_hash(char *input){
 25     int i = 0;
 26     Trie* path = root;
 27     while(input[i] != 0){
 28         if(path->next[input[i] - 'a'] == NULL){
 29             path->next[input[i] - 'a'] = (Trie*)malloc(sizeof(Trie)); 
 30             trie_init(path->next[input[i] - 'a']);
 31         }    
 32         path = path->next[input[i] - 'a'];
 33         i ++;
 34     }
 35     if(path->flag == true){
 36         return path->trie_index;
 37     }else{
 38         path->flag = true;
 39         path->trie_index = trie_index ++;
 40         return path->trie_index;
 41     }
 42 
 43 }
 44 int find_set(int i){
 45     if(trie_set[i] == i)
 46         return i;
 47     return  find_set(trie_set[i]);
 48 
 49 }
 50 void union_set(int i, int j){
 51     int i_p = find_set(i);
 52     int j_p = find_set(j);
 53     if(i_p == j_p) return;
 54     if(trie_rank[i_p] > trie_rank[j_p])
 55         trie_set[j_p] = i_p;
 56     else{
 57         if(trie_rank[i_p] == trie_rank[j_p])
 58             trie_rank[j_p]++;
 59         trie_set[i_p] = j_p;
 60     }
 61     
 62 
 63 }
 64 int main(int argc, char* argv[]){
 65     trie_index = 0;
 66     vector<int> trie_degree(500000,0);
 67     char a[12], b[12];
 68     root = (Trie*)malloc(sizeof(Trie)); 
 69     trie_init(root);
 70     for(int i = 0; i < 500000; i ++){
 71         trie_set.push_back(i);
 72         trie_rank.push_back(0);
 73     }
 74     while (scanf("%s%s",a,b)!=EOF){
 75         int i = trie_hash(a);
 76         int j = trie_hash(b);    
 77         trie_degree[i] += 1;
 78         trie_degree[j] += 1;
 79 
 80         union_set(i, j);
 81     
 82     }
 83     int pre = find_set(0);
 84     bool result = true;    
 85     for(int i = 1; i < trie_index; i ++)
 86         if(find_set(i) != pre)
 87             result = false;
 88     int odd_num = 0;
 89     for(int i = 0; i < trie_index; i ++){
 90         if((trie_degree[i] & 1) == 1)
 91             odd_num += 1;
 92     }
 93     if(odd_num== 1 || odd_num > 2)
 94             result = false;
 95     if(result == true)
 96         cout << "Possible" << endl;
 97     else
 98         cout << "Impossible" << endl;
 99     return 0;
100 }

样本输入

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible