Cod sursa(job #948410)

Utilizator marius135Dumitran Adrian Marius marius135 Data 10 mai 2013 11:25:42
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 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;
}