Cod sursa(job #2153248)

Utilizator amaliarebAmalia Rebegea amaliareb Data 6 martie 2018 02:12:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int MaxN = 100005;
int n, m;
int onst[MaxN], low[MaxN];
bitset<MaxN> viz;
vector<int> gr[MaxN], tati[MaxN];
stack<int> st;
vector<vector<int> > comps;

void Ctc(int node) {
    viz[node] = 1;
    st.push(node);
    onst[node] = st.size();
    low[node] = onst[node];
    for (auto son: gr[node]) {
        if (!viz[son]) {
            Ctc(son);
            low[node] = min(low[node], low[son]);
        }
        else if (onst[son]) low[node] = min(low[node], onst[son]);
    }
    if (low[node] == onst[node]) {
        vector<int> v;
        while (st.top() != node) {
            v.push_back(st.top());
            onst[st.top()] = 0;
            st.pop();
        }
        st.pop();
        v.push_back(node);
        onst[node] = 0;
        comps.push_back(v);
    }
}

int main() {
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        f >> x >> y;
        gr[x].push_back(y);
    }
    for (int i = 1; i <= n; ++i) if (!viz[i]) Ctc(i);
    g << comps.size() << '\n';
    for (auto v: comps) {
        for (auto x: v) g << x << ' ';
        g << '\n';
    }
    return 0;
}