Submission #3234405

---

Source Code Expand

//test
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <set>
using namespace std;

void read(int &x)
{
	char ch=getchar();bool f=0;x=0;
	while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	if(f)x=-x;
} 

void read(long long &x)
{
	char ch=getchar();bool f=0;x=0;
	while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	if(f)x=-x;
}

struct graph_t
{
	int front,nex;
}graph[201001],graph2[201001],graph3[201001];
int tail=1000,tail2=1000,tail3=1000;

void addedge(int u,int v)
{
	int tmp=graph[u].nex;
	graph[u].nex=++tail;
	graph[tail].front=v;
	graph[tail].nex=tmp;
}

void addedge2(int u,int v)
{
	int tmp=graph2[u].nex;
	graph2[u].nex=++tail2;
	graph2[tail2].front=v;
	graph2[tail2].nex=tmp;
}

void addedge3(int u,int v)
{
	int tmp=graph3[u].nex;
	graph3[u].nex=++tail3;
	graph3[tail3].front=v;
	graph3[tail3].nex=tmp;
}

int vis[1001];
pair<int,int> edge[200001];
int nfinish=0;
int finish[1001];
int nconnect=0;
int connect[1001];
int indegree[1001],outdegree[1001];
int cnt[1001][1001];

void dfs1(int now)
{
	vis[now]=1;
	for(int i=graph[now].nex;i;i=graph[i].nex)
	{
		if(vis[graph[i].front]!=1)
		{
			dfs1(graph[i].front);
		}
	}
	finish[nfinish++]=now;
}

void dfs2(int now)
{
//	printf("dfs2(%d)\n",now);
	vis[now]=2;
	connect[now]=nconnect;
	for(int i=graph2[now].nex;i;i=graph2[i].nex)
	{
		if(vis[graph2[i].front]!=2)
		{
			dfs2(graph2[i].front);
		}
	}
}

void dfs3(int from,int now)
{
	for(int i=graph3[now].nex;i;i=graph3[i].nex)
	{
		cnt[from][graph3[i].front]+=cnt[from][now];
		dfs3(from,graph3[i].front);
	}
}

int main()
{
	int n,m;
	read(n);read(m);
	for(int i=0;i<m;i++)
	{
		int from,to;
		read(from);read(to);
		addedge(from,to);
		addedge2(to,from);
		edge[i]=make_pair(from,to);
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]!=1)dfs1(i);
	}
	for(int i=nfinish-1;i>=0;i--)
	{
		if(vis[finish[i]]!=2)
		{
			nconnect++;
			dfs2(finish[i]);
		}
	}
/*	for(int i=1;i<=n;i++)
	{
		cout<<connect[i]<<" ";
	}
	cout<<endl;*/
	for(int i=1;i<=n;i++)
	{
		for(int j=graph[i].nex;j;j=graph[j].nex)
		{
			if(connect[i]==connect[graph[j].front])
			{
				outdegree[i]++;
			}
		}
		for(int j=graph2[i].nex;j;j=graph2[j].nex)
		{
			if(connect[i]==connect[graph2[j].front])
			{
				indegree[i]++;
			}
		} 
	}
/*	for(int i=1;i<=n;i++)
	{
		printf("in:%d,out:%d\n",indegree[i],outdegree[i]);
	}*/
	for(int i=0;i<m;i++)
	{
		int from=edge[i].first,to=edge[i].second;
		if(connect[from]!=connect[to])addedge3(connect[from],connect[to]);
	}
	for(int i=1;i<=nconnect;i++)
	{
		cnt[i][i]=1;
		dfs3(i,i);
	}
/*	for(int i=1;i<=nconnect;i++)
	{
		for(int j=1;j<=nconnect;j++)
		{
			cout<<cnt[i][j];
		}
		cout<<endl;
	}*/
	for(int i=0;i<m;i++)
	{
		int from=edge[i].first,to=edge[i].second;
		if(connect[from]==connect[to])
		{
			if(indegree[to]==1||outdegree[from]==1)
			{
				puts("diff");
			}
			else
			{
				puts("same");
			}
		}
		else
		{
			if(cnt[connect[from]][connect[to]]>1)
			{
				puts("diff");
			}
			else
			{
				puts("same");
			}
		}
	}
	return 0;
}
/*
3 3
1 2
1 3
2 3

2 2
1 2
2 1
*/

Submission Info

Judge Result