Cod sursa(job #327035)

Utilizator TyberFMI Dogan Adrian Ioan Lucian Tyber Data 26 iunie 2009 21:36:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
#define nmax 200001
using namespace std;
int min(int,int);
vector<int> adj[nmax],con,idx,lowlink,in_stack;
vector<vector<int> > c;
stack<int> s;
int ind;
void tarjan(int n,vector<int>*adj)
{
	idx[n]=lowlink[n]=ind;
	ind++;
	s.push(n);
	in_stack[n]=1;
	vector<int>::const_iterator it;
	for(it=adj[n].begin();it!=adj[n].end();it++)
	{
		if(idx[*it]==-1)
		{
			tarjan(*it,adj);
			lowlink[n]=min(lowlink[n],lowlink[*it]);
		}
		else
			if(in_stack[*it])
				lowlink[n]=min(lowlink[n],lowlink[*it]);
	}
	if(idx[n]==lowlink[n])
	{
		con.clear();
		int nod;
		do
		{
			con.push_back(nod=s.top());
			s.pop();
			in_stack[nod]=0;
		}
		while(nod!=n);
		c.push_back(con);
	}
}
int main()
{
	int n,m,x,y,i,j;
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(;m;m--)
	{
		scanf("%d %d",&x,&y);
		adj[x-1].push_back(y-1);
	}
	idx.resize(n);
	lowlink.resize(n);
	in_stack.resize(n);
	idx.assign(n,-1);
	in_stack.assign(n,0);
	for(i=0;i<n;i++)
		if(idx[i]==-1)
			tarjan(i,adj);
	printf("%d\n",c.size());
	for(i=0;i<c.size();i++)
	{
		for(j=0;j<c[i].size();j++)
			printf("%d ",c[i][j]+1);
		printf("\n");
	}
	return 0;
}
int min(int a,int b)
{
	if(a<b)
		return a;
	else 
		return b;
}