Cod sursa(job #935649)

Utilizator marius135Dumitran Adrian Marius marius135 Data 4 aprilie 2013 13:13:08
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;
#define maxn 5001


char m[maxn][maxn];
int sel[maxn];
int nr_ctc, n;
vector <int> sol[maxn];

void df(int a){
	sel[a] = 1;
	sol[nr_ctc].push_back(a);
	for( int i = 1; i <= n; ++i)
		if( sel[i] == 0 && m[a][i])
			df(i);

}
int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	int  mm;
	scanf("%d %d", &n, &mm);
	for( int i = 1; i <= mm; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		m[a][b] = 1;
	}
	
	for( int k = 1; k <= n; ++k)
		for( int i = 1; i <= n; ++i)
			for( int j = 1; j <= n; ++j) 
				m[i][j] |= (m[i][k] & m[k][j]);
	for( int i = 1; i <= n; ++i)
		for( int j = 1; j <= n; ++j)
			m[i][j] &= m[j][i];
	
	for( int i = 1; i <= n; ++i)
		if( sel[i] == 0) {
			df(i);
			nr_ctc++;
		}
	cout<<nr_ctc<<endl;
	for( int i = 0; i < nr_ctc; ++i) {
		for( int j = 0; j < sol[i].size(); ++j) {
			cout<<sol[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}