洛谷 P1333：瑞瑞的木棍 ← 欧拉回路 + 并查集

【题目来源】https://www.luogu.com.cn/problem/P1333【题目描述】瑞瑞有一堆的玩具木棍每根木棍的两端分别被染上了某种颜色现在他突然有了一个想法想要把这些木棍连在一起拼成一条线并且使得木棍与木棍相接触的两端颜色都是相同的给出每根木棍两端的颜色请问是否存在满足要求的排列方式。例如如果只有 2 根木棍第一根两端的颜色分别为 red 和 blue第二根两端的颜色分别为 red 和 yellow那么 blue --- red | red --- yellow 便是一种满足要求的排列方式。【输入格式】输入有若干行每行包括两个单词表示一根木棍两端的颜色单词由小写字母组成且单词长度不会超过 10 个字母最多有 250000 根木棍。​​​​​​​【输出格式】如果木棒能够按要求排列输出 Possible否则输出 Impossible。​​​​​​​【输入样例】blue redred violetcyan blueblue magentamagenta 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 N5e510; 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 afind(x); int bfind(y); if(a!b) pre[a]b; } int main() { for(int i0; iN; i) pre[i]i; unordered_mapstring,int mp; int idx0; string s1,s2; while(cins1s2) { if(mp.find(s1)mp.end()) mp[s1]idx; if(mp.find(s2)mp.end()) mp[s2]idx; int ump[s1],vmp[s2]; du[u],du[v]; merge(u,v); } int nidx; if(n0) { coutPossibleendl; return 0; } int rootfind(0); for(int i1; in; i) { if(find(i)!root) { coutImpossibleendl; return 0; } } int odd0; for(int i0; in; i) { if(du[i]%21) odd; } if(odd0 || odd2) { coutPossibleendl; } else coutImpossibleendl; return 0; } /* in: blue red red violet cyan blue blue magenta magenta cyan out: Possible */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/160909877https://blog.csdn.net/hnjzsyjyj/article/details/160888941https://blog.csdn.net/hnjzsyjyj/article/details/149031663https://blog.csdn.net/hnjzsyjyj/article/details/140747624