花椰菜君给了蒜头君 n 个单词，如果一个单词的最后一个字母和另一个单词的第一个字母相同，那么两个单词就可以连接在一起组成一个新的单词。现在花椰菜君想要蒜头君计算一下，给定的 n 个单词是否可以全部连接在一起。
输入格式
第一行输入一个整数 n，代表一共有 n 个单词（1≤n≤100,000）。
接下来输入 nn行，每行输入一个单词。单词均由小写字母组成，每个单词长度不超过 20。
输出格式
输出一行，如果所有的单词都可以连接在一起并且可以形成一个环，那么输出Euler loop；如果所有单词都可以连接在一起，但是不会形成环，输出Euler path；如果所有单词不能连在一起，那么输出impossible。
样例输入
3 euler ruby jisuanke
样例输出
Euler path
分析:这道题的整体思路要想对，我们不应该从单词向单词连边，一是因为存不下，二是因为这就构成了一个哈密顿
图问题，这是不能直接得出结论的。可以发现，一个单词只有首尾有用，我们从每个单词的首字母向末字母连一条有
向边，因为如果是欧拉图，保证每个单词经过一次就好了，这里就是每条边经过一次就好了，而不是之前的每个点经
过一次，就可以求解了。注意：判断之前一定要看一下图是不是连通的，并查集就可以了.
#include <cstdio> #include <queue> #include <cstring> #include <iostream> #include <algorithm> #include <string> #include <cmath> using namespace std; int n,chu[200],ru[200],zifu[200],tot,fa[200]; int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } bool check(int c) { for (int i = 1; i <= tot; i++) if (zifu[i] == c) return true; return false; } int main() { for (int i = 'a';i <= 'z'; i++) fa[i] = i; scanf("%d", &n); for (int i = 1; i <= n; i++) { char s[25]; scanf("%s", s); int len = strlen(s); if (!check(s[0])) zifu[++tot] = s[0]; if (!check(s[len - 1])) zifu[++tot] = s[len - 1]; ru[s[len - 1]]++; chu[s[0]]++; int x = find(s[0]); int y = find(s[len - 1]); fa[x] = y; } if (n == 1) printf("Euler path"); else { bool flag1 = 0, flag2 = 0; int ans = 0; for (int i = 1; i <= tot; i++) { if (find(zifu[i]) != fa[zifu[1]]) { flag1 = 1; //不连通 break; } int t = abs(chu[zifu[i]] - ru[zifu[i]]); if (t != 0) flag2 = 1; //不是回路 if (t == 1) ans++; if (t >= 2) { flag1 = 1; break; } } if (flag1) printf("impossible"); else if (!flag2) printf("Euler loop"); else if (ans == 2) printf("Euler path"); else printf("impossible"); } return 0; }