Submission #3231528

---

Source Code Expand

//save code
#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];
int tail=1000,tail2=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[tail].front=v;
	graph2[tail].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];

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

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);
		addedge(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[i]!=2)
		{
			nconnect++;
			dfs2(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=graph[i].nex;j;j=graph[j].nex)
		{
			if(connect[j]==connect[graph[j].front])
			{
				outdegree[i]++;
			}
		}
		for(int j=graph2[i].nex;j;j=graph2[j].nex)
		{
			if(connect[j]==connect[graph2[j].front])
			{
				indegree[i]++;
			}
		}
	}
	
/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<vis[i][j]<<" ";
		}
		cout<<endl;
	}*/
	
	return 0;
}
/*
3 3
1 2
1 3
2 3

2 2
1 2
2 1
*/

Submission Info

Judge Result