Submission #3231438

---

Source Code Expand

#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=10*x+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int Maxn=1005;
const int Maxm=200005;
struct Edge
{
	int u,v,next;
} w[Maxm<<1];
int cnt,head[Maxn];
int n,m,vis[Maxn][Maxn];
bool used[Maxm];
void AddEdge(int u,int v)
{
	cnt++;
	w[cnt].u=u;
	w[cnt].v=v;
	w[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int start,int x)
{
	if(used[x])	return;
	vis[start][x]++;
	used[x]=true;
	for(int i=head[x]; i; i=w[i].next)
	{
		dfs(start,w[i].v);
	}
	used[x]=false;
}
void init()
{
	n=read();
	m=read();
	for(int i=1; i<=m; i++)
	{
		int a=read();
		int b=read();
		AddEdge(a,b);
	}
	for(int i=1; i<=n; i++)
	{
		memset(used,0,sizeof(used));
		dfs(i,i);
	}
}
inline bool SSC(int u,int v)
{
	return vis[u][v] && vis[v][u];
}
int main()
{
	init();
	for(int i=1; i<=m; i++)
	{
		int from=w[i].u;
		int to=w[i].v;
		if(SSC(from,to))
		{
			if(vis[from][to]==1)
			{
				puts("diff");
			}
			else
			{
				puts("same");
			}
		}
		else
		{
			if(vis[from][to]>1)
			{
				puts("diff");
			}
			else
			{
				puts("same");
			}
		}
	}
	return 0;
}
/*
3 3
1 2
1 3
2 3

2 2
1 2
2 1

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5
*/

Submission Info

Judge Result