Cod sursa(job #385743)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 23 ianuarie 2010 13:26:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <vector>
using namespace std;

const int n_max = 100001;

vector <int> v[n_max],
			 c[n_max];

int r[n_max],
	d[n_max],
	viz[n_max];
int time = 0, k = 0, n, m;
void df(int x)
{
	vector <int>::iterator it;

	viz[x] = 1;
	++time;
	d[x] = time; //Depth
	r[x] = time; //Reach
	
	for (it = v[x].begin(); it!=v[x].end(); ++ it)
	{
		if (!viz[*it])
		{
			df(*it);
			r[x] = min(r[x],r[*it]);
		}
		else
			r[x] = min(r[x],r[*it]);
	}
	c[k].push_back(x);
	if (d[x] == r[x])
		++k;
}

int main()
{
	int a,b;
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++ i)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
	}
	for (int i = 1; i <= n; ++ i)
		if (!viz[i])
			df(i);
	printf("%d\n", k);
	for (int i = 0; i < k; ++ i, printf("\n"))
		for (int j = 0; j < c[i].size(); ++ j)
			printf("%d ", c[i][j]);

	return 0;
}