Cod sursa(job #2121267)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 3 februarie 2018 15:13:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
bool hz[100001],in_stiva[100001];
int n,m,low[100001],lev[100001],ctc,nr,a,b;
vector<int> v[100001],stiva,componente[100001];
void dfs (int knot) {
    stiva.push_back(knot);
    hz[knot] = 1;
    in_stiva[knot] = 1;
    low[knot] = ++nr;
    lev[knot] = nr;
    for (int i = 0; i < v[knot].size(); i ++) {
        int vecin = v[knot][i];
        if (hz[vecin] == 0) {
            dfs (vecin);
        }
        if (in_stiva[vecin] == 1) {
            if (low[vecin] < low[knot]) {
                low[knot] = low[vecin];
            }
        }
    }

    if (lev[knot] == low[knot]) {
        ctc ++;
        while (stiva.size() != 0 && stiva[stiva.size()-1] != knot) {
            componente[ctc].push_back ( stiva[stiva.size()-1]);
            in_stiva[stiva[stiva.size()-1]] = 0;
            stiva.pop_back();
        }
        componente[ctc].push_back ( stiva[stiva.size()-1]);
        in_stiva[stiva[stiva.size()-1]] = 0;
        stiva.pop_back();
    }

}
int main (void) {
    in >> n >> m;
    for (int i = 1; i <= m; i ++) {
        in >> a >> b;
        v[a].push_back (b);
    }
    nr = 0;
    for (int i = 1; i <= n; i ++) {
        if (hz[i] == 0) {
            dfs (i);
        }
    }
    out << ctc <<"\n";
    for (int i = 1; i <= ctc; i ++) {
        for (int j = 0; j < componente[i].size(); j ++) {
            out <<componente[i][j] <<" ";
        }
        out <<"\n";
    }
    return 0;
}