Cod sursa(job #3287414)

Utilizator BucsMateMate Bucs BucsMate Data 17 martie 2025 22:00:46
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int INF = 1000*1000*1000;

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

bool in_stack[100001] = {};
vector<int> disc(100001, INF);
vector<int> low(100001, INF);
stack<int> st;
vector<vector<int>> comps;
int time = 1;

void DFS_tarjan(int node, vector<vector<int>> &adj)
{
    disc[node] = time;
    low[node] = disc[node];
    time++;
    st.push(node);
    in_stack[node] = true;

    for(int i = 0; i < adj[node].size(); i++){
        int newNode = adj[node][i];

        if(disc[newNode] == INF){
            DFS_tarjan(newNode, adj);
            low[node] = min(low[node], low[newNode]);
        }
        else if(in_stack[newNode]){
            low[node] = min(low[node], disc[newNode]);
        }
    }

    if(low[node] == disc[node]){
        vector<int> comp;
        int curr_node = st.top();
        comp.push_back(curr_node);
        st.pop();
        in_stack[curr_node] = false;
        while(curr_node != node){
            curr_node = st.top();
            comp.push_back(curr_node);
            st.pop();
            in_stack[curr_node] = false;
        }
        comps.push_back(comp);
    }
}

int main()
{
    int N, M;
    fin >> N >> M;
    vector<vector<int>> adj(N+1);
    for(int i = 0; i < M; i++){
        int a, b;
        fin >> a >> b;
        adj[a].push_back(b);
    }
    for(int i = 1; i <= N; i++){
        if(disc[i] == INF){
            DFS_tarjan(i, adj);
        }
    }

    fout << comps.size() << endl;
    for(int i = 0; i < comps.size(); i++){
        for(int j = 0; j < comps[i].size(); j++){
            fout << comps[i][j] << " ";
        }
        fout << endl;
    }
    return 0;
}