Cod sursa(job #1335121)

Utilizator FapFapAdriana FapFap Data 5 februarie 2015 01:09:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define nmax 100005
using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

vector <int> v[nmax], transpose[nmax], components[nmax];
stack <int> s;

int n, m, nr=0;
bool seen[nmax];

void get_data(){
    int x, y;
    fin >> n >> m;
    for(int i=1; i<=m; i++){
        fin >> x >> y;
        v[x].push_back(y);
        transpose[y].push_back(x);
    }
}

void print_data(){
    fout << nr << "\n";
    for(int i=1; i<=nr; i++){
        for(int j=0; j<components[i].size(); j++)
            fout << components[i][j] << " ";
        fout << "\n";
    }
}

void topo(int x){
    seen[x]= true;
    for(int i=0; i<v[x].size(); i++)
        if(!seen[v[x][i]])  seen[v[x][i]]= true, topo(v[x][i]);
        s.push(x);
}
void kosaraju(int x){
    seen[x]= true;
    components[nr].push_back(x);
    for(int i=0; i<transpose[x].size(); i++)
        if(!seen[transpose[x][i]])
            seen[transpose[x][i]]= true, kosaraju(transpose[x][i]);
}

void second_main(){
    for(int i=1; i<=n; i++){
        if(!seen[i])    topo(i);
    }
    for(int i=1; i<=n; i++) seen[i]= false;
    while(!s.empty()){
        if(!seen[s.top()]){
            nr++;
            kosaraju(s.top());
        }
        s.pop();
    }
}

int main(){
    get_data();
    second_main();
    print_data();
    return 0;
}