hdu 3926 hand in hand(简化版图的同构)
题意就是判断两个图是否同构，标准的判断图的同构是很难的，不过这个题却是例外。
每个kid都只有两只手，也就是说每个点的度最大为2，这个是解题的关键！每个点的度最大为2，也就是说图上只存在三种形态：独立的点，链跟环。
这样问题就简单了，分别找出两个图中的点，链跟环，分别比较时否完全相同即可。
#include<algorithm>#include<iostream>#include<cstring>#include<fstream>#include<sstream>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<queue>#include<stack>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define debug puts("**debug**")#define LL long long#define PB push_back#define MP make_pair#define eps 1e-10using namespace std;const int maxn = 10010;int n, m, u, v, dfs_clock;vector<int> G[maxn], t1, t2;bool vis[maxn];int in[maxn];void dfs(int u){ vis[u] = 1; dfs_clock++; REP(i, G[u].size()) { int v = G[u][i]; if(!vis[v]) dfs(v); }}int main(){ int T; scanf("%d", &T); FF(kase, 1, T+1) { t1.clear(); t2.clear(); scanf("%d%d", &n, &m); REP(i, n) G[i].clear(); CLR(in, 0); while(m--) { scanf("%d%d", &u, &v); u--; v--; G[u].PB(v); G[v].PB(u); in[u]++, in[v]++; } CLR(vis, 0); //先找独立的点 或者链 REP(i, n) if(in[i] < 2 && !vis[i]) { vis[i] = 1; dfs_clock = 0; dfs(i); t1.PB(dfs_clock); } //剩下的就都是环了 REP(i, n) if(!vis[i]) { vis[i] = 1; dfs_clock = 0; dfs(i); t1.PB(dfs_clock + 10000); } scanf("%d%d", &n, &m); REP(i, n) G[i].clear(); CLR(in, 0); while(m--) { scanf("%d%d", &u, &v); u--; v--; G[u].PB(v); G[v].PB(u); in[u]++, in[v]++; } CLR(vis, 0); REP(i, n) if(in[i] < 2 && !vis[i]) { vis[i] = 1; dfs_clock = 0; dfs(i); t2.PB(dfs_clock); } REP(i, n) if(!vis[i]) { vis[i] = 1; dfs_clock = 0; dfs(i); t2.PB(dfs_clock + 10000); } sort(t1.begin(), t1.end()); sort(t2.begin(), t2.end()); int a = t1.size(), b = t2.size(); bool flag = 0; if(a != b) flag = 1; REP(i, a) if(t1[i] != t2[i]) { flag = 1; break; } printf("Case #%d: %s\n", kase, flag ? "NO" : "YES"); } return 0;}