Cod sursa(job #2357921)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 27 februarie 2019 20:12:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define pb push_back

using namespace std;

const int MAXN = 100010;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, ind[MAXN], link[MAXN], nr, compNr;
bool inStack[MAXN];
vector<int> edges[MAXN], comp[MAXN];
stack<int> s;

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        edges[x].pb(y);
    }
}

inline int doMin(int a, int b) {
    return (a < b ? a : b);
}

void doDfs(int vertix) {
    s.push(vertix);
    inStack[vertix] = true;
    link[vertix] = ind[vertix] = ++nr;
    for (auto &it: edges[vertix]) {
        if (!ind[it]) {
            doDfs(it);
            link[vertix] = doMin(link[it], link[vertix]);
        }
        else if (inStack[it] == true) {
            link[vertix] = doMin(ind[it], link[vertix]);
        }
    }
    if (link[vertix] == ind[vertix]) {
        compNr++;
        while(!s.empty()) {
            int top = s.top();
            s.pop();
            inStack[top] = false;
            comp[compNr].pb(top);
            if (top == vertix) {
                break;
            }
        }
    }
}

void solve() {
    for (int i = 1; i <= n; ++i) {
        if (!ind[i])
            doDfs(i);
    }
}

void print() {
    fout << compNr << "\n";
    for (int i = 1; i <= compNr; ++i) {
        for (auto &it: comp[i]) {
            fout << it << " ";
        }
        fout << "\n";
    }
}

int main() {
    read();
    solve();
    print();
    return 0;
}