Cod sursa(job #1958946)

Utilizator razvandRazvan Dumitru razvand Data 8 aprilie 2017 21:50:46
Problema Componente tare conexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

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

vector<int> v[100003];
int disc[100003];
int low[100003];
int tim;
stack<int> S;
vector<int> s[100003];
bitset<100003> ins;
int C;

void dfs(int nod) {

    disc[nod] = ++tim;
    low[nod] = disc[nod];
    S.push(nod);
    ins[nod] = true;

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

    if(low[nod] == disc[nod]) {

        C++;
        int Q = S.top();

        while(Q != nod) {
            Q = S.top();
            ins[Q] = false;
            s[C].push_back(Q);
            S.pop();
        }

    }

}

int main() {

    int n,m;
    in >> n >> m;
    int x,y;

    for(int i = 1; i <= m; i++) {
        in >> x >> y;
        v[x].push_back(y);
    }

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

    out << C << '\n';

    for(int i = 1; i <= C; i++) {
        for(int j = 0; j < s[i].size(); j++) {
            out << s[i][j] << " ";
        }
        out << '\n';
    }

    return 0;
}