Cod sursa(job #2592204)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 1 aprilie 2020 13:12:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

vector<vector<int>> ans;
vector<int> comp, graf[MAXN];
int niv[MAXN], mnniv[MAXN];
bool viz[MAXN];
stack<pair<int, int>> stk;

void biconex(int nod){
    comp.clear();
    pair<int, int> vf = {0, 0};
    while(vf.first != nod){
        vf = stk.top();
        stk.pop();
        comp.push_back(vf.second);
    }
    comp.push_back(nod);
    ans.push_back(comp);
}

void dfs(int prec, int nod){
    viz[nod] = 1;
    niv[nod] = niv[prec] + 1;
    mnniv[nod] = niv[nod];
    for(auto x: graf[nod]){
        if(!viz[x]){
            stk.push({nod, x});
            dfs(nod, x);
            mnniv[nod] = min(mnniv[nod], mnniv[x]);
            if(mnniv[x] >= niv[nod]) biconex(nod);
        }
        else if(x != prec) mnniv[nod] = min(mnniv[nod], niv[x]);
    }
}

int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        if(!viz[i]){
            stk.push({0, i});
            dfs(0, i);
        }
    }
    fout << ans.size() << "\n";
    for(auto x: ans){
        for(auto y: x) fout << y << " ";
        fout << "\n";
    }
    return 0;
}