Cod sursa(job #549126)

Utilizator IAmASuperCerealVictor Andrei IAmASuperCereal Data 8 martie 2011 10:13:03
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<vector>
#define N 200001
#define input "ctc.int"
#define output "ctc.out"
using namespace std;

vector<int> s[N];
vector<int> p[N];
vector<int> c[N];

int m,n,nr;
bool v1[N],v2[N];
int ordine[N];

void open()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);
}
void read()
{
	int x,y,a;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		s[x].push_back(y);
		p[y].push_back(x);
	}
}

void dfs1(int x)
{
	int a;
	v1[x] = true;
	for(int i=0;i<s[x].size();++i)
	{
		a = s[x][i];
		if(!v1[a])
			dfs1(a);
	}
	ordine[++nr] = x;
}

void dfs2(int x)
{
	int a;
	v2[x] = true;
	c[nr].push_back(x);
	for(int i=0;i<p[x].size();++i)
	{
		a = p[x][i];
		if(!v2[a])
			dfs2(a);
	}
}

void _where_the_magic_happens()
{
	for(int i=1;i<=n;i++)
		if(!v1[i])
			dfs1(i);
	nr = 0;
	for(int i=n;i>=1;i--)
		if(!v2[ordine[i]])
		{
			++nr;
			dfs2(ordine[i]);
		}
	printf("%d\n",nr);
	for(int i=1;i<=nr;i++)
	{
		for(size_t j=0 ; j<c[i].size() ; j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}
}
int main()
{
	
	open();
	read();
	_where_the_magic_happens();
	return 0;
}