Cod sursa(job #935643)

Utilizator marius135Dumitran Adrian Marius marius135 Data 4 aprilie 2013 13:05:59
Problema Componente tare conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<stack>

using namespace std;
#define maxn 100001



int sel[maxn];
int nr_ctc, n;
stack <int> parc;
vector <int> sol[maxn];
vector <int> vec[maxn];
vector <int> vect[maxn];

void afisare_sol(){
	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;
	}
	
}

void df(int a){
	sel[a] = 1;
	for( int i = 0; i < vec[a].size(); ++i)
		if( sel[vec[a][i]] == 0)
			df(vec[a][i]);
	parc.push(a);
	
}
void df2(int a){
	sel[a] = 1;
	sol[nr_ctc].push_back(a);
	
	for( int i = 0; i < vect[a].size(); ++i)
		if( sel[vect[a][i]] == 0)
			df2(vect[a][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);
		vec[a].push_back(b);
		vect[b].push_back(a);
	}
	
	for( int i = 1; i <= n; ++i)
		if( sel[i] == 0) {
			df(i);
		}
	memset(sel, 0, sizeof(sel));
	
	while( ! parc.empty() ){ 
		int val = parc.top();
		parc.pop();
		if( sel[val] == 0) {
			df2(val);
			nr_ctc++;
		}
	}		
		
	afisare_sol();
	return 0;
}