Cod sursa(job #2140432)

Utilizator osiaccrCristian Osiac osiaccr Data 23 februarie 2018 14:46:58
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <vector>
#include <stack>
#define DEF 100010

using namespace std;

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

vector < int > L[DEF];

vector < vector < int > > SCCs;

stack < int > St;

int n, m, low[DEF], disc[DEF];

bool in_stack[DEF];

void dfs (int u) {
    static int time = 0;

    disc[u] = low[u] = ++ time;
    St.push (u);
    in_stack[u] = true;

    for (int i = 0; i < L[u].size (); ++ i) {
        int v = L[u][i];
        if (disc[v] == 0) {
            dfs (v);
            low[u] = min (low[u], low[v]);
        }
        else {
            if (in_stack[v] == true) {
                low[u] = min (low[u], disc[v]);
            }
        }
    }

    if (disc[u] == low[u]) {
        int w = 0;
        vector < int > SCC;
        while (w != u) {
            w = St.top ();
            SCC.push_back (w);
            St.pop ();
            in_stack[w] = false;
            w = St.top ();
        }
        w = St.top ();
        SCC.push_back (w);
        in_stack[w] = 0;
        St.pop ();
        SCCs.push_back (SCC);
    }
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        L[x].push_back (y);
    }

    for (int i = 1; i <= n; ++ i) {
        if (disc[i] == 0) {
            dfs (i);
        }
    }

    fout << SCCs.size () << '\n';
    for (int i = 0; i < SCCs.size (); ++ i) {
        for (int j = 0; j < SCCs[i].size (); ++ j) {
            fout << SCCs[i][j] << " ";
        }
        fout << "\n";
    }

    return 0;
}