Cod sursa(job #2664885)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 29 octombrie 2020 17:33:15
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

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

vector <int> g[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, numberOfAP;
int discoverTime[1 + NMAX], lowLink[1 + NMAX], dfsParent[1 + NMAX];
bool isArticulationPoint[1 + NMAX];

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;
         
            ArticulationPointsDFS(to); 

            if(isArticulationPoint[from] == false && lowLink[to] >= discoverTime[from]) {
                isArticulationPoint[from] = true;
                numberOfAP ++; /// De verificat repetitii, da am trebuie verificat
            }

            lowLink[from] = min(lowLink[from], lowLink[to]);
        } else {
            /// De repetat asta
            if(to != dfsParent[from])
                lowLink[from] = min(lowLink[from], lowLink[to]);
        }
    }
}

void solve() {
    for(int i = 1; i <= n; i ++) {
        if(discoverTime[i] == 0) {
            dfsRoot = i;
            rootsNumberOfChildren = 0;
            ArticulationPointsDFS(dfsRoot);
            if(isArticulationPoint[dfsRoot] == false && rootsNumberOfChildren > 1) {
                numberOfAP ++; /// Si aici aveam repetitii
                isArticulationPoint[dfsRoot] = true;
            }
        }
    }
}

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

bool visited[1 + NMAX];

void dfsAfisare(int from) {
    printf("%d ", from);
    visited[from] = true;

    for(auto &to : g[from]) {
        if(visited[to] == false && isArticulationPoint[to] == false) {
            dfsAfisare(to);
        }
    }
}

void afisare() {
    printf("%d\n", numberOfAP + 1);
    for(int i = 1; i <= n; i ++) {
        if(isArticulationPoint[i] == true) {
            // dfsAfisare(i);
            // printf("\n");
        }   
    }
}

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

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

    return 0;
}