Cod sursa(job #2808323)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 24 noiembrie 2021 21:45:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;

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

stack < int > st;
bool in_stack[100005];
int n,m;
vector < int > v[100005];
int x,y;
int viz[100005];
int low[100005];
int nr_ctc;
vector < int > ctcs[100005];
int ids[100005],id;

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

void dfs(int nod) {
    st.push(nod);
    in_stack[nod]=1;
    viz[nod]=1;
    low[nod]=++id;
    ids[nod]=id;
    for (auto k:v[nod]) {
        if (viz[k]==0) {
            dfs(k);
        }
        if (in_stack[k]==1) {
            low[nod]=min(low[nod],low[k]);
        }
    }
    if (low[nod]==ids[nod]) {
        nr_ctc++;
        ctcs[nr_ctc].push_back(nod);
        while (st.top()!=nod) {
            in_stack[st.top()]=0;
            ctcs[nr_ctc].push_back(st.top());
            st.pop();
        }
        in_stack[nod]=0;
        st.pop();
    }
}

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

void show() {
    g << nr_ctc << '\n';
    for (int i=1;i<=nr_ctc;i++) {
        for (auto k:ctcs[i]) {
            g << k << " ";
        }
        g << '\n';
    }
}

int main()
{
    read_graph();
    tarjan();
    show();
    return 0;
}