Cod sursa(job #3222166)

Utilizator ililogIlinca ililog Data 9 aprilie 2024 10:05:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
using namespace std;
#include<iostream>
#include <fstream>
#include<vector>
#include<stack>
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, x, y;
vector<int> G[100005];
int d[100005]; ///numarul de ordine al nodului
int low[100005]; ///primul varf ce poate fi atins pe un lant alternativ
int tata[100005]; ///tatal nodului
bool viz[100005];
int timp;
stack<pair<int,int>> st;
vector<int> c;
vector< vector<int> > comp;

void read() {
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void dfs_l(int nod) {
    low[nod] = d[nod] = ++timp; ///initializez low cu timpul de ajungere in nod
    for (auto k: G[nod]) {
        if (d[k] == 0) { ///nu am vizitat k
            tata[k] = nod;
            dfs_l(k);
            low[nod] = min(low[nod], low[k]); ///compar cu nodul la care poate ajunge k
        } else if (k != tata[nod]) {
            low[nod] = min(low[nod], d[k]); ///am mai vizitat nodul, am ajuns la el pe un lant alternativ
        }
    }
}

void creare_componenta(int a, int b) {
    
    c.clear();
    int nod = st.top().first, fiu = st.top().second;
    while (nod != a || fiu != b) {
        c.push_back(fiu);
        st.pop();
        nod = st.top().first, fiu = st.top().second;
    }
    st.pop();
    c.push_back(fiu);
    c.push_back(nod);
    comp.push_back(c);
}

void dfs(int nod) {
    viz[nod] = 1;
    for (auto k: G[nod]) {
        if (!viz[k]) {
            st.push({nod, k}); ///adaug muchie
            dfs(k);
            if (low[k] >= d[nod]) { ///nod este punct de articulatie, nu pot ajunge din k la noduri mai sus ca el
                creare_componenta(nod, k);
            }
        }
    }
}

void solve() {
    
    for (int i = 1; i<=n; i++) {
        if (d[i] == 0) {
            dfs_l(i);
        }
    }
    
    for (int i = 1; i<=n; i++) {
        if (!viz[i]) {
            dfs(i);
        }
    }
}

void print() {
    fout << comp.size() << "\n";
    for (auto x: comp) {
        for (auto y: x) {
            fout << y << " ";
        }
        fout << "\n";
    }
}

int main() { 
    read();
    solve();
    print();
    return 0;
}