记录编号	250177	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	树木园	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.475 s
提交时间	2016-04-14 17:41:32	内存使用	10.99 MiB

#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#define N 100010
using namespace std;
ifstream in("cactus.in");
ofstream out("cactus.out");
vector<int> F[N],G[N];
int n,m;
bool flag=1;
int mod=1000007;
int M;
class node
{
public:
	int s[N];
}A[11],B[11];
bool operator <(node a,node b)
{
	for(int i=1;i<=n;i++)return a.s[i]<b.s[i];
	return 1;
}
void read()
{
	int i,u,v;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		A[1].s[u]++;
		A[1].s[v]++;
	}
	for(i=1;i<=m;i++)
	{
		in>>u>>v;
		F[u].push_back(v);
		F[v].push_back(u);
		B[1].s[u]++;
		B[1].s[v]++;
	}
	M=min(1000,10000000/(n*20));
	M=max(M,10);
}
void work()
{
	int i,j,k,u,v;
	for(k=2;k<=M;k++)
	{
	    for(i=1;i<=n;i++)
	    {
		    u=i;
		    for(j=0;j<G[u].size();j++)
		    {
			    v=G[u][j];
			    A[2].s[u]+=A[1].s[v];
			    A[2].s[u]%=mod;
		    }
	    }
		for(i=1;i<=n;i++)
	    {
		    u=i;
		    for(j=0;j<F[u].size();j++)
		    {
			    v=F[u][j];
			    //if(k==2)out<<u<<' '<<v<<endl;
			    B[2].s[u]+=B[1].s[v];
			    B[2].s[u]%=mod;
		    }
	    }
		A[1]=A[2];
		B[1]=B[2];
		sort(A[2].s,A[2].s+n+1);
		sort(B[2].s,B[2].s+n+1);
		/*for(i=1;i<=n;i++)out<<A[2].s[i]<<' ';
		out<<endl;
		for(i=1;i<=n;i++)out<<B[2].s[i]<<' ';
		out<<endl;*/
		for(i=1;i<=n;i++)
	    {
		    if(A[2].s[i]!=B[2].s[i])
		    {
			    flag=0;
			    break;
		    }
	    }
		for(i=1;i<=n;i++)A[2].s[i]=0;
		for(i=1;i<=n;i++)B[2].s[i]=0;
		if(!flag)break;
	}
	
	if(flag)out<<"YES"<<endl;
	else out<<"NO"<<endl;
}
int main()
{
	read();
	work();
	return 0;
}