Cod sursa(job #2663424)

Utilizator DawlauAndrei Blahovici Dawlau Data 26 octombrie 2020 12:52:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;
using pii = pair <int, int>;


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


vector < vector <int> > g;
vector <int> lowlink, depth;
vector < set <int> > comps;
int V, E;

stack <pii> Stack;

void readData(){

    fin >> V >> E;

    g.resize(V + 1);
    lowlink.resize(V + 1);
    depth.resize(V + 1);
    comps.reserve(V);

    for(int e = 0; e < E; ++e){

        int u, v;
        fin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }
}


void cacheBC(const pii &edge){

    pii stackEdge;

    set <int> BC;

    do{

        stackEdge = Stack.top();
        Stack.pop();

        BC.insert(stackEdge.first);
        BC.insert(stackEdge.second);


    }while(stackEdge != edge);
    comps.push_back(BC);
}


void DFS(int node, int dad, int d){

    depth[node] = lowlink[node] = d;

    for(const int &adj : g[node])
        if(adj != dad){
            if(depth[adj] == 0){

                Stack.push({node, adj});
                DFS(adj, node, d + 1);

                lowlink[node] = min(lowlink[node], lowlink[adj]);

                if(lowlink[adj] >= depth[node])
                    cacheBC({node, adj});
            }
            else lowlink[node] = min(lowlink[node], depth[adj]);
        }
}


int main(){

    readData();

    for(int node = 1; node <= V; ++node) // even though it is connected
        if(depth[node] == 0)
            DFS(node, 0, 1);


    // printing

    comps.resize(comps.size());
    fout << comps.size() << '\n';

    for(int c = 0; c < (int)comps.size(); ++c){

        for(const int &node : comps[c])
            fout << node << ' ';
        fout << '\n';
    }
}