学步园

传送门：【HDU】3926 Hand in Hand

题目大意：给你两个无向图，问你是否同构。

题目分析：本题很特殊，每个点最多两个度，那么也就是说要么环，要么链，要么点。

那么我们并查集一下，统计每个环中的节点数，每个链中的节点数，最后拍个序比较一下就好，只要一个不一样就不是同构的。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )

const int MAXN = 10005 ;
const int MAXQ = 10005 ;
const int MAXE = 20005 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int v , c , n ;
	Edge () {}
	Edge ( int var , int cost , int next ) :
		v ( var ) , c ( cost ) , n ( next ) {}
} ;

struct Node {
	int num ;
	int f ;
	bool operator < ( const Node &a ) const {
		return f != a.f ? f > a.f : num > a.num ;
	}
} ;

Node a[2][MAXN] ;
int n , m ;
int deg[2][MAXN] ;
int p[MAXN] ;

int find ( int x ) {
	return p[x] == x ? x : ( p[x] = find ( p[x] ) ) ;
}

void work () {
	int x , y ;
	clear ( a , 0 ) ;
	REP ( o , 2 ) {
		scanf ( "%d%d" , &n , &m ) ;
		REPF ( i , 1 , n )
			a[o][i].num = 1 , p[i] = i ;
		REP ( i , m ) {
			scanf ( "%d%d" , &x , &y ) ;
			int xx = find ( x ) ;
			int yy = find ( y ) ;
			if ( xx == yy )
				a[o][xx].f = 1 ;
			else {
				p[xx] = yy ;
				a[o][yy].num += a[o][xx].num ;
				a[o][xx].num = 0 ;
			}
		}
		sort ( a[o] + 1 , a[o] + n + 1 ) ;
	}
	int flag = 0 ;
	REP ( i , MAXN )
		if ( a[0][i].num != a[1][i].num || a[0][i].f != a[1][i].f )
			flag = 1 ;
	if ( flag )
		printf ( "NO\n" ) ;
	else
		printf ( "YES\n" ) ;
}	

int main () {
	int T , cas ;
	for ( scanf ( "%d" , &T ) , cas = 1 ; cas <= T ; ++ cas ) {
		printf ( "Case #%d: " , cas ) ;
		work () ;
	}
	return 0 ;
}