Cod sursa(job #2758884)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 13 iunie 2021 22:40:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <vector>
#include <stack>
 
using namespace std;
 
ifstream f("ctc.in");
ofstream g("ctc.out");
 
vector <int> adj[100005];
int n, m, timestamp;
vector<vector<int>> ctcs;
 
void dfs(int node, vector<int> &found, vector<int> &low_link, stack<int> &nodes_stack, vector<bool> &in_stack){
    found[node] = ++timestamp;
    low_link[node] = timestamp;
    nodes_stack.push(node);
    in_stack[node] = true;
 
    for (int neigh : adj[node]){
        if (found[neigh] != 0 &&  in_stack[neigh]){
            low_link[node] = min(low_link[node], low_link[neigh]);
        }
        if (found[neigh] != 0)
            continue;
        dfs(neigh, found, low_link, nodes_stack, in_stack);
        low_link[node] = min(low_link[node], low_link[neigh]);
        
    }
    if(low_link[node] == found[node])
        {
            vector<int> ctc;
            while(true){
                int top = nodes_stack.top();
                nodes_stack.pop();
                in_stack[top] = false;
                ctc.push_back(top);
 
                if (top == node){
                    break;
                }
            }
            ctcs.push_back(ctc);
        }
}
 
void tarjan(int n, int m){
 
    vector<int> low_link (n + 1, 0);
    vector<int> found(n+1, 0);
    stack<int> nodes_stack;
    vector<bool> in_stack(n+1, 0);
 
    for (int i = 1 ; i <= n; i ++){
        if (found[i] == 0){
            dfs(i, found, low_link, nodes_stack, in_stack);
        }
    }
}
 
int main(){
    f >> n >> m;
    for (int i = 0 ; i < m; i ++){
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
    }
 
    tarjan(n, m);
 
    g << ctcs.size() << '\n';
    for(auto ctc : ctcs){
        for(int c : ctc){
            g << c << " ";
        }
        g << '\n';
    }
 
 
 
}