Cod sursa(job #1318546)

Utilizator AnesthesicChereches Sergiu Alexandru Anesthesic Data 16 ianuarie 2015 07:37:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100001
using namespace std;

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

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

bool seen[nmax];

int c, n, m;

void dfs(int x){
    seen[x] = true;
    for(int i=0; i<v[x].size(); i++)
        if(!seen[v[x][i]])
            dfs(v[x][i]);
    s.push(x);
}

void kosajaru(int x){
    seen[x] = true;
    components[c].push_back(x);
    for(int i=0; i<transpose[x].size(); i++){
        if(!seen[transpose[x][i]])
            kosajaru(transpose[x][i]);
    }
}

int main(){
    int x, y, i;
    fin >> n >> m;
    for(int i=1; i<=m; i++){
        fin >> x >> y;
        v[x].push_back(y); // the adjency list
        transpose[y].push_back(x); // the transpose adjency list
    }

    for(int i=1; i<=n; i++)
        if(!seen[i])    dfs(i); // the first dfs on the original graph

    for(int i=1; i<=n; i++) seen[i] = false;
    while(!s.empty()){
        if(!seen[s.top()]){
            c++;
            kosajaru(s.top());
        }
        s.pop();
    }
    fout << c << "\n";
    for(int i=1; i<=c; i++){
        for(int j=0; j<components[i].size(); j++)
            fout << components[i][j] << " ";
    fout << "\n";
    }
    return 0;
}