Cod sursa(job #2919959)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 21 august 2022 00:29:09
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;

void dfs(int node, int level, vector<int>& minLevel,
         stack<int>& st, vector<bool>& isInStack,
         vector<vector<int>>& ctc, vector<vector<int>>& G){
    if(minLevel[node] >= 0){
        return;
    }
    minLevel[node] = level;
    st.push(node);
    isInStack[node] = true;
    for(int child: G[node]){
        dfs(child, level + 1, minLevel, st, isInStack, ctc, G);
        if(isInStack[child]){
            minLevel[node] = min(minLevel[node], minLevel[child]);
        }
    }

    if(level == minLevel[node]){
        ctc.push_back({});
        int x = -1;
        do{
            x = st.top();
            st.pop();
            isInStack[x] = false;
            ctc.back().push_back(x);
        }while(x != node);
    }
}

int main(){
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");

    int N, M;
    cin >> N >> M;

    vector<vector<int>> G(N + 1);
    int x, y;
    for(int i = 1; i <= M; ++i){
        cin >> x >> y;
        G[x].push_back(y);
    }

    vector<int> minLevel(N + 1, -1);
    stack<int> st;
    vector<bool> isInStack(N + 1, false);
    vector<vector<int>> ctc;
    for(int node = 1; node <= N; ++node){
        if(minLevel[node] < 0){
            dfs(node, 0, minLevel, st, isInStack, ctc, G);
        }
    }

    cout << ctc.size() << "\n";
    for(vector<int>& nodes: ctc){
        for(int node: nodes){
            cout << node << " ";
        }
        cout << "\n";
    }

    cin.close();
    cout.close();
    return 0;
}