Cod sursa(job #929477)

Utilizator taigi100Cazacu Robert taigi100 Data 27 martie 2013 01:10:11
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
#define max 100005
int n,m,nrc;
struct node
{
	int index,lowlink,vis;
}nodes[max];
vector<int> roads[max],componente[max];
stack<int> S;
int ind;
void strongconnect(int v)
{
	nodes[v].index=ind;
	nodes[v].lowlink=ind;
	nodes[v].vis=1;
	ind+=1;
	S.push(v);

	for(vector<int>::iterator it=roads[v].begin();it!=roads[v].end();it++)
		if(nodes[*it].vis==0)
		{
			strongconnect( *it );
			nodes[v].lowlink= min(nodes[v].lowlink,nodes[*it].lowlink);
		}
		else 
			nodes[v].lowlink=min(nodes[v].lowlink,nodes[*it].lowlink);

	if(nodes[v].lowlink==nodes[v].index)
	{
		int qw;
		nrc++;
		do
		{
			qw=S.top();
			componente[nrc].push_back(qw);
			S.pop();
		} while( qw!=v );
	}
}
void trajan()
{
	ind=0;
	for( int i=1;i<=n;i++)
		if( nodes[i].index == 0 )
			strongconnect( i );
}
int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

	scanf("%d%d",&n,&m);

	int a,b;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		roads[a].push_back(b);
	}

	trajan();

	printf("%d\n",nrc);
	for(int i=1;i<=nrc;i++)
	{
		for(vector<int>::iterator it=componente[i].begin(); it!=componente[i].end();it++)
			printf("%d ",*it);
		printf("\n");
	}
	return 0;
}