Cod sursa(job #2665021)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 29 octombrie 2020 21:46:49
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.05 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>

using namespace std;

const int NMAX = 1e5;

// ---------- CITIRE ------------

vector <int> g[1 + NMAX];
vector <int> rasp[1 + NMAX];
int n, m;

void citire() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++) {
        int u, v;
        scanf("%d%d", &u, &v);

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

// ---------- REZOLVARE ---------

int currentTime, dfsRoot, rootsNumberOfChildren, nrComponenteBiconexe;
int discoverTime[1 + NMAX], lowLink[1 + NMAX], dfsParent[1 + NMAX];
bool isArticulationPoint[1 + NMAX];
stack <pair<int, int>> myStack;

void ArticulationPointsDFS(int from) {
    discoverTime[from] = lowLink[from] = ++currentTime;

    for(auto &to: g[from]) {
        if(discoverTime[to] == 0) {
            dfsParent[to] = from;
            if(from == dfsRoot) ++rootsNumberOfChildren;

            myStack.push(make_pair(from, to));
            ArticulationPointsDFS(to); 

            if(lowLink[to] >= discoverTime[from]) {
                isArticulationPoint[from] = true;
                while(myStack.top().first != from || myStack.top().second != to) {
                    rasp[nrComponenteBiconexe].push_back(myStack.top().first);
                    rasp[nrComponenteBiconexe].push_back(myStack.top().second);
                    myStack.pop();
                }
                rasp[nrComponenteBiconexe].push_back(from);
                rasp[nrComponenteBiconexe].push_back(to);
                myStack.pop();
                nrComponenteBiconexe ++;
            }

            lowLink[from] = min(lowLink[from], lowLink[to]);
        } else {
            /// De repetat asta
            if(to != dfsParent[from]) {
                lowLink[from] = min(lowLink[from], lowLink[to]);
                if(discoverTime[to] < discoverTime[from]) {
                    // myStack.push(make_pair(from, to));
                }
            }
        }
    }
}

void solve() {
    for(int i = 1; i <= n; i ++) {
        if(discoverTime[i] == 0) {
            dfsRoot = i;
            rootsNumberOfChildren = 0;
            ArticulationPointsDFS(dfsRoot);
            isArticulationPoint[dfsRoot] = (rootsNumberOfChildren > 1);
            if(myStack.empty() == false) {
                while(!myStack.empty()) {
                    rasp[nrComponenteBiconexe].push_back(myStack.top().first);
                    rasp[nrComponenteBiconexe].push_back(myStack.top().second);
                    myStack.pop();
                }
            }
        }
    }
}

// ---------- AFISARE -----------

void afisare() {
    printf("%d\n", nrComponenteBiconexe);
    for(int i = 0; i < nrComponenteBiconexe; i ++) {
        sort(rasp[i].begin(), rasp[i].end());
        rasp[i].erase(unique(rasp[i].begin(), rasp[i].end()), rasp[i].end());
        for(auto &nod: rasp[i]) {
            printf("%d ", nod);
        }
        printf("\n");
    }
}

int main() {
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    citire();
    solve();
    afisare();

    return 0;
}