Cod sursa(job #796609)

Utilizator lianaliana tucar liana Data 11 octombrie 2012 21:29:29
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 100005
long n, m, i, x, y, viz[nmax], tac, vf[nmax], comp, j;
vector <int> ma[nmax], mat[nmax], rez[nmax];
vector <int>::iterator it;

void citire()
{
	scanf("%ld %ld",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld",&x,&y);
		ma[x].push_back(y);
		mat[y].push_back(x);
	}
}

void dfs1(long nod)
{
	vector<int>::iterator it;
	viz[nod]=1;
	for (it=ma[nod].begin();it!=ma[nod].end();it++)
		if (viz[*it]==0)
			dfs1(*it);
	vf[++tac]=nod;
}

void dfs2(long nod)
{
	vector<int>::iterator it;
	viz[nod]=2;
	for (it=mat[nod].begin();it!=mat[nod].end();it++)
		if (viz[*it]<2)
			dfs2(*it);
	rez[comp].push_back(nod);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	for (i=1;i<=n;i++)
		if (!viz[i])
			dfs1(i);
	for (i=n;i>=1;i--)
		if (viz[vf[i]]<2)
		{
			comp++;	ma[comp][0]=0;
			dfs2(vf[i]);
		}
	printf("%ld\n",comp);
	for (i=1;i<=comp;i++)
	{
		for (it=rez[i].begin();it!=rez[i].end();it++)
			printf("%ld ",*it);
		printf("\n");
	}
	return 0;
}