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;}