洛谷 P1333：瑞瑞的木棍 ← 欧拉回路 + 并查集
【题目来源】
https://www.luogu.com.cn/problem/P1333
【题目描述】
瑞瑞有一堆的玩具木棍，每根木棍的两端分别被染上了某种颜色，现在他突然有了一个想法，想要把这些木棍连在一起拼成一条线，并且使得木棍与木棍相接触的两端颜色都是相同的，给出每根木棍两端的颜色，请问是否存在满足要求的排列方式。
例如，如果只有 2 根木棍，第一根两端的颜色分别为 red 和 blue，第二根两端的颜色分别为 red 和 yellow，那么 blue --- red | red --- yellow 便是一种满足要求的排列方式。
【输入格式】
输入有若干行，每行包括两个单词，表示一根木棍两端的颜色，单词由小写字母组成，且单词长度不会超过 10 个字母，最多有 250000 根木棍。
【输出格式】
如果木棒能够按要求排列，输出 Possible，否则输出 Impossible。
【输入样例】
blue red
red violet
cyan blue
blue magenta
magenta cyan
【输出样例】
Possible
【数据范围】
单词长度不会超过 10 个字母，最多有 250000 根木棍。
【算法分析】
（一）这是一个图论问题，可以建模为无向图的欧拉路径/欧拉回路存在性问题。具体地，每个颜色是一个顶点，每根木棍是一条边，问题转化为：是否存在一条路径（或回路）能经过每条边恰好一次。这需要检查两个条件：
1. 连通性：所有边对应的顶点必须属于同一个连通分量。
2. 度（奇度数顶点数量）：
• 如果所有顶点的度都是偶数，则存在欧拉回路（从任意点出发可回到起点）。
• 如果恰好有两个顶点的度是奇数，则存在欧拉路径（从一个奇度点出发，另一个结束）。
• 其他情况（奇度顶点数不是 0 或 2）则不可能。
由于颜色用字符串表示，需用 map 或 unordered_map 映射为数字编号。并查集检查连通性。
（二）用 mp 将颜色字符串映射为整数编号（从 0 开始）。
• 每读入一根木棍（c1 c2），对应顶点 u 和 v 的度加 1，并在并查集中合并。
• 读完后，检查所有出现过的顶点是否连通（即属于同一个并查集）。
• 统计奇度顶点个数，若为 0 或 2 则输出 Possible，否则输出 Impossible。
【算法代码】
#include <bits/stdc++.h> using namespace std; const int N=5e5+10; int pre[N]; int du[N]= {0}; int find(int x) { if(x!=pre[x]) pre[x]=find(pre[x]); return pre[x]; } void merge(int x,int y) { int a=find(x); int b=find(y); if(a!=b) pre[a]=b; } int main() { for(int i=0; i<N; i++) pre[i]=i; unordered_map<string,int> mp; int idx=0; string s1,s2; while(cin>>s1>>s2) { if(mp.find(s1)==mp.end()) mp[s1]=idx++; if(mp.find(s2)==mp.end()) mp[s2]=idx++; int u=mp[s1],v=mp[s2]; du[u]++,du[v]++; merge(u,v); } int n=idx; if(n==0) { cout<<"Possible"<<endl; return 0; } int root=find(0); for(int i=1; i<n; i++) { if(find(i)!=root) { cout<<"Impossible"<<endl; return 0; } } int odd=0; for(int i=0; i<n; i++) { if(du[i]%2==1) odd++; } if(odd==0 || odd==2) { cout<<"Possible"<<endl; } else cout<<"Impossible"<<endl; return 0; } /* in: blue red red violet cyan blue blue magenta magenta cyan out: Possible */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160909877
https://blog.csdn.net/hnjzsyjyj/article/details/160888941
https://blog.csdn.net/hnjzsyjyj/article/details/149031663
https://blog.csdn.net/hnjzsyjyj/article/details/140747624