Cod sursa(job #3210462)

Utilizator devilexeHosu George-Bogdan devilexe Data 6 martie 2024 12:00:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;
vector<int> G[MAXN + 1];
vector<int> idx;
vector<int> lowlink;
vector<bool> viz;
vector<bool> check;
stack<int> st;
int N, M, GIDX;
vector <vector <int>> sol;

void tarjan(int node) {
    ++GIDX;
    st.emplace(node);
    check[node] = 1;
    viz[node] = 1;
    idx[node] = GIDX;
    lowlink[node] = GIDX;
    for ( const auto& vecin: G[node]) {
        if (!viz[vecin] ) {
            tarjan(vecin);
            lowlink[node] = min(lowlink[node], lowlink[vecin]);
        }
        else {
            if ( check[vecin] ) {
                lowlink[node] = min(lowlink[node], idx[vecin]);
            }
        }
    }
    if ( lowlink[node] == idx[node] ) {
        int top;
        vector <int> ctc;
        do {
            top = st.top();
            st.pop();
            check[top] = 0;
            ctc.emplace_back(top);
        }
        while ( top != node);
        sol.emplace_back(ctc); 
    }
}



int main() {
    fin >> N >> M;
    idx.resize(N + 1);
    lowlink.resize(N + 1);
    viz.resize(N + 1, false);
    check.resize(N + 1, false);
    int x, y;
    while(M--) {
        fin >> x >> y;
        G[x].push_back(y);
    }
    for ( int i = 1; i <= N; ++ i) {
        if ( !viz[i] ) {
            tarjan(i);
        }
    }
    fout << sol.size() << '\n';
    for ( const auto& comp: sol) {
        for ( const auto& elem: comp ) {
            fout << elem << " ";
        }
        fout << '\n';
    }
}