Cod sursa(job #2576792)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 6 martie 2020 22:59:15
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int maxn = 200005;
vector <int> bicon[maxn];
vector <int> v[maxn];
int minback[maxn];
int niv[maxn];
int stk[maxn];
int conexe, sz;
void dfs(int nod, int tata)
{
    stk[++sz] = nod;
    for(auto it : v[nod])
    {
        if(niv[it] == 0)
        {
            int act = sz;
            niv[it] = niv[nod] + 1;
            minback[it] = niv[nod] + 1;
            dfs(it, nod);
            minback[nod] = min(minback[nod], minback[it]);
            if(minback[it] >= niv[nod])
            {
                bicon[++conexe].push_back(nod);
                while(sz > act)
                {
                    bicon[conexe].push_back(stk[sz]);
                    sz--;
                }
            }
        }
        else if(it != tata)
            minback[nod] = min(minback[nod], niv[it]);
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    niv[1] = 1;
    dfs(1, 0);
    out << conexe << "\n";
    for(int i = 1; i <= conexe; i++, out << "\n")
        for(auto it : bicon[i])
            out << it << " ";
    return 0;
}