Cod sursa(job #497046)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 1 noiembrie 2010 15:36:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<vector>
#define N 100010
using namespace std;
vector<int> v[N],C[N],stiva;
int n,m,i,a,b,viz[N],low[N],dsfnum[N],top,num,nc;
void read(),solve(),visit(int);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("ctc.in","rt",stdin);
	freopen("ctc.out","wt",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
	}
}
void solve()
{
	vector<int>::iterator it;
	for(i=1;i<=n;i++)
		if(!viz[i])
		{
			num=0;
			visit(i);
		}
	printf("%d",nc);
	for(i=1;i<=nc;i++)
	{
		printf("\n");
		for(it=C[i].begin();it!=C[i].end();it++)
			printf("%d ",*it);
	}
	printf("\n");
}
void visit(int p)
{
	int nod;
	vector<int>::iterator it;
    viz[p]=1;
    stiva.push_back(p);//add p to L
    dsfnum[p]=++num;//increment N
    low[p]=dsfnum[p];
    for(it=v[p].begin();it!=v[p].end();it++)
    {
		if(viz[*it]==2)continue;
		if(!viz[*it]) visit(*it);
		low[p]=(low[p]<low[*it])?low[p]:low[*it];
    }
    if(low[p]==dsfnum[p])
    {
		nc++;
		for(;;)
		{
			nod=stiva.back();
			viz[nod]=2;
			C[nc].push_back(nod);
			stiva.pop_back();
			if(nod==p)break;
		}
    }
}