[ create a new paste ] login | about

Link: http://codepad.org/rUWfLs0t    [ raw code | output | fork ]

didyxdi - C++, pasted on Sep 3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<cctype>
using namespace std;

int n,m;
vector<int> g[10005],rg[10005],vs;
int k;
bool used[10005];
int cmp[10005];
int u,num;

void init()
{
	memset(g,0,sizeof(g));
	memset(rg,0,sizeof(rg));
	k=0;
	u=0;num=0;
}

void dfs(int i)
{
	used[i]=true;
	for(int j=0;j<g[i].size();j++)
	if(!used[g[i][j]]) dfs(g[i][j]);
	vs.push_back(i);
}

void rdfs(int i,int x)
{
	used[i]=true;
	cmp[i]=x;
	for(int j=0;j<rg[i].size();j++)
	if(!used[rg[i][j]]) rdfs(rg[i][j],x); 
}

int scc()
{
	memset(used,false,sizeof(used));
	vs.clear();//*
	for(int i=1;i<=n;i++)
	if(!used[i]) dfs(i);
	memset(used,false,sizeof(used));
	int p=0;
	for(int i=vs.size()-1;i>=0;i--)
	if(!used[vs[i]]) rdfs(vs[i],++p);
	return p;
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		for(int i=1;i<=m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			g[x].push_back(y);
			rg[y].push_back(x);
		}
		k=scc();
		
		for(int i=1;i<=n;i++)
		{
			if(cmp[i]==k)
			{
				u=i;
				num++;
			}
		}
		
		memset(used,false,sizeof(used));
		rdfs(u,0);
		for(int i=1;i<=n;i++)
		if(!used[i]) 
		{
			num=0;
			break;
		}
		
		printf("%d\n",num);
	}
	return 0;
} 


Output:
1
2
3
4
5
cc1plus: warnings being treated as errors
In function 'void dfs(int)':
Line 34: warning: comparison between signed and unsigned integer expressions
In function 'void rdfs(int, int)':
Line 43: warning: comparison between signed and unsigned integer expressions


Create a new paste based on this one


Comments: