Cod sursa(job #422239)

Utilizator NemultumituMatei Ionita Nemultumitu Data 22 martie 2010 13:22:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define pb push_back
using namespace std;
struct triplet
{
	int ti,to,nod;
};
vector <int> pred[100100],succ[100100],ct[100100];
triplet t[100100];
int n,m,timp,cnt;
bool v[100100];

bool comp(const triplet &a,const triplet &b)
{
	return a.to>b.to;
}

void dfsinv(int nod)
{
	v[nod]=true;
	ct[cnt].pb(nod);
	for (int i=0;i!=pred[nod].size();++i)
		if (!v[pred[nod][i]])
			dfsinv(pred[nod][i]);
}

void dfs(int nod)
{
	t[nod].nod=nod;
	t[nod].ti=++timp;
	v[nod]=true;
	for (int i=0;i!=succ[nod].size();++i)
		if (!v[succ[nod][i]])
			dfs(succ[nod][i]);
	t[nod].to=++timp;
}

void citire()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		pred[y].pb(x);
		succ[x].pb(y);
	}
}

void scrie()
{
	printf("%d\n",cnt);
	for (int i=1;ct[i].size();++i)
	{
		for (int j=0;j!=ct[i].size();++j)
			printf("%d ",ct[i][j]);
		printf("\n");
	}
}

int main()
{
	freopen ("ctc.in","r",stdin);
	freopen ("ctc.out","w",stdout);
	citire();
	for (int i=1;i<=n;++i)
		if (!v[i])
			dfs(i);
	sort(t+1,t+n+1,comp);
	memset(v,0,sizeof(v));
	for (int i=1;i<=n;++i)
		if (!v[t[i].nod])
		{
			++cnt;
			dfsinv(t[i].nod);
		}
	scrie();
	return 0;
}