Cod sursa(job #2178863)

Utilizator TooHappyMarchitan Teodor TooHappy Data 19 martie 2018 19:30:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;
  
ifstream in("biconex.in");
ofstream out("biconex.out");

vector< vector< int > > G, componenteBiconexe;
vector< int > discoveryTime, lowestTime;
stack< pair< int, int > > s;

void updateBiconnectedComponents(int u, int v) {
    vector< int > newComponent;
    int tempU, tempV;

    do {
        tempU = s.top().first; tempV = s.top().second; s.pop();
        newComponent.push_back(tempU); newComponent.push_back(tempV);
    } while(tempU != u || tempV != v);

    componenteBiconexe.push_back(newComponent);
}

void DFS(int node, int fatherNode, int currentTime) {
    discoveryTime[node] = lowestTime[node] = currentTime;

    for(auto vecin: G[node]) {
        if(vecin == fatherNode) {
            continue;
        }

        if(discoveryTime[vecin] == -1) {
            s.push(make_pair(node, vecin));
            DFS(vecin, node, currentTime + 1);

            lowestTime[node] = min(lowestTime[node], lowestTime[vecin]);
            if(lowestTime[vecin] >= discoveryTime[node]) {
                updateBiconnectedComponents(node, vecin);
            }
        } else {
            lowestTime[node] = min(discoveryTime[vecin], lowestTime[node]);
        }
    }
}

int main() {

    int n, m; in >> n >> m;

    G.resize(n + 1); discoveryTime.resize(n + 1); discoveryTime.assign(n + 1, -1); lowestTime.resize(n + 1);
    for(int i = 1; i <= m; ++i) {
        int x, y; in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    DFS(1, 0, 0);

    out << (int)componenteBiconexe.size() << '\n';
    for(int i = 0; i < (int)componenteBiconexe.size(); ++i) {
        map< int, bool > printed;

        for(int j = 0; j < (int)componenteBiconexe[i].size(); ++j) {
            if(!printed[componenteBiconexe[i][j]]) {
                out << componenteBiconexe[i][j] << " ";
                printed[componenteBiconexe[i][j]] = true;
            }
        }
        out << '\n';
        printed.clear();
    }
    

    in.close(); out.close();
  
    return 0;
}