Cod sursa(job #935669)

Utilizator marius135Dumitran Adrian Marius marius135 Data 4 aprilie 2013 13:29:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
#include<iostream>
#include<fstream>
#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 <vector <int> > sol;
vector <int> vec[maxn];
vector <int> vect[maxn];

void afisare_sol(){
	ofstream out("ctc.out");
  
    out << sol.size() << "\n";
    for (size_t i = 0; i < sol.size(); ++ i) {
        for (size_t j = 0; j < sol[i].size(); ++ j)
            out << sol[i][j] << " ";
        out << "\n";
    }
    out.close();
}

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[sol.size() - 1].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;
	cin>>n>>mm;
	for( int i = 1; i <= mm; ++i) {
		int a, b;
		cin>>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) {
			vector<int> temp;
			sol.push_back(temp);
			df2(val);
			
			
		}
	}		
		
	afisare_sol();
	return 0;
}