Cod sursa(job #384124)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 19 ianuarie 2010 10:33:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 100020
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); ++i)
vector <int> G[NMAX], Gt[NMAX], S[NMAX];
int t[NMAX], T[NMAX];
bool ok[NMAX];
int n , m, c;
void dfs1(int x){
	if(ok[x]) return;
	ok[x] = true;
	FOR(i, G[x])
		dfs1(*i);
	t[++t[0]] = x;
	
}
void dfs2(int x){
	if(ok[x]) return;
	ok[x] = true;
	T[x] = c;
	FOR(i, Gt[x])
		dfs2(*i);
}
void afisare(){
	printf("%d\n", c);
	for(int i = 1; i <= n; ++i)
		S[T[i]].push_back(i);
	for(int i = 1; i <= c; ++i){
		FOR(it, S[i])
			printf("%d ", *it);
		printf("\n");
	}
}
int main(){
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i){
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		Gt[y].push_back(x);
	}
	for(int i = 1; i <= n; ++i)
		//if(!ok[i]) 
			dfs1(i);
	//int c = 0;
	memset(ok, 0, sizeof(ok));
	for(int i = t[0]; i; --i)
		if(!T[t[i]]){
			c++;
			dfs2(t[i]);
		}
	afisare();
}