Cod sursa(job #2749247)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 6 mai 2021 00:42:14
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

vector <int> adj[100005];
int n, m, timestamp;
vector<set<int>> ctcs;

void dfs(int node, vector<int> &found, vector<int> &low_link, stack<pair<int,int>> &edges_stack){
    found[node] = ++timestamp;
    low_link[node] = timestamp;

    for (int neigh : adj[node]){
        if (found[neigh] != 0){
            low_link[node] = min(low_link[node], found[neigh]);
        }
        if (found[neigh] != 0)
            continue;
        edges_stack.push(make_pair(node, neigh));
        dfs(neigh, found, low_link, edges_stack);
        low_link[node] = min(low_link[node], low_link[neigh]);
        if (low_link[neigh] >= found[node]){
            set<int> ctc;
            while(true){
                auto top = edges_stack.top();
                edges_stack.pop();
                ctc.insert(top.first);
                ctc.insert(top.second);

                if (top.first == node && top.second == neigh){
                    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;
    stack<pair<int,int>> edges_stack;
    vector<bool> in_stack(n+1, 0);

    for (int i = 1 ; i <= n; i ++){
        if (found[i] == 0){
            dfs(i, found, low_link, edges_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(auto c : ctc){
            g << c << " ";
        }
        g << '\n';
    }



}