Cod sursa(job #929511)

Utilizator taigi100Cazacu Robert taigi100 Data 27 martie 2013 01:52:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
#define mi(a,b) ((a)<(b) ? (a) : (b))
#define max 100005
int n,m,nrc;
struct node
{
	int index,lowlink,vis;
	node()
	{
		index=-1;
		lowlink=0;
		vis=0;
	}
}nodes[max];
vector<int> roads[max],componente;
stack<int> S;
vector< vector<int> > final;
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].index==-1)
		{
			strongconnect( *it );
			nodes[v].lowlink= mi(nodes[v].lowlink,nodes[*it].lowlink);
		}
		else if( nodes[*it].vis==1 )
			nodes[v].lowlink=mi(nodes[v].lowlink,nodes[*it].lowlink);

	if(nodes[v].lowlink==nodes[v].index)
	{
		int qw;
		componente.clear();
		do
		{
			qw=S.top();
			componente.push_back(qw);
			nodes[qw].vis=0;
			S.pop();
		} while( qw!=v );
		final.push_back(componente);
	}
}
void trajan()
{
	ind=0;
	for( int i=0;i<n;i++)
		if( nodes[i].index == -1 )
			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=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		roads[a-1].push_back(b-1);
	}

	trajan();

	printf("%d\n",final.size());
    
	for(size_t i=0;i<final.size();i++)
	{
		for(size_t j=0;j<final[i].size();j++)
			printf("%d ",final[i][j]+1);
		printf("\n");
	}
	return 0;
}