Cod sursa(job #3269128)

Utilizator abelesefBurduhos Abel abelesef Data 18 ianuarie 2025 11:19:55
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,a,b,nod[100005],on_st[100005],low[100005],cnt = 1;
vector<int> adj[100005];
stack<int> st;
vector<vector<int>> compf;

void tarjan(int node) {
        nod[node] = cnt;
        low[node] = cnt;
        cnt++;
        st.push(node);
        on_st[node] = 1;
        for (auto el : adj[node]) {
                if (nod[el] == 0) {
                        tarjan(el);
                }
                if (on_st[el]) {
                        low[node] = min(low[node], low[el]);
                }
        }

        if (low[node]==nod[node]) {
                vector<int> comp;
                int crt;
                do {
                        crt = st.top();
                        st.pop();
                        on_st[crt] = 0;
                        comp.push_back(crt);
                } while(crt!=node);
                compf.push_back(comp);
        }
}

int main() {
        fin>>n>>m;
        for (int i = 1;i<=m;++i) {
                fin>>a>>b;
                adj[a].push_back(b);
        }
        for (int i = 1;i<=n;++i) {
                if (nod[i]==0) {
                        tarjan(i);
                }
        }
        fout<<compf.size()<<'\n';
        for (const auto &comp : compf) {
                for (auto el : comp) {
                        fout<<el<<" ";
                }
                fout<<'\n';
        }
        return 0;
}