Cod sursa(job #2929248)

Utilizator DooMeDCristian Alexutan DooMeD Data 25 octombrie 2022 12:51:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;

vector<vector<int>> dx(nmax+5);
int idx[nmax+5], lowlink[nmax+5], timer = 0;
stack<int> st;
bool onstack[nmax+5];

int nr = 0;
vector<vector<int>> comp;

void dfs(int node) {
    idx[node] = timer; lowlink[node] = timer;
    timer++;
    st.emplace(node); onstack[node] = true;
    for(auto next : dx[node]) {
        if(idx[next] == -1) 
            dfs(next);
        if(onstack[next])
            lowlink[node] = min(lowlink[node], lowlink[next]);
    }

    if(idx[node] == lowlink[node]) {
        nr++;
        int curr;
        vector<int> temp;
        do {
            curr = st.top(); st.pop();
            onstack[curr] = false;
            temp.emplace_back(curr);
        } while(curr != node);
        comp.emplace_back(temp);
    }
}

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

    int n, m; f >> n >> m;
    for(int i=1; i<=m; i++) {
        int x, y; f >> x >> y;
        dx[x].emplace_back(y);
    }
    for(int i=1; i<=n; i++) idx[i] = -1;
    for(int i=1; i<=n; i++) if(idx[i] == -1) dfs(i);
    g << nr << "\n";
    for(int i=0; i<nr; i++, g << "\n")
        for(auto x : comp[i]) 
            g << x << " ";
    return 0;
}