Cod sursa(job #2382830)

Utilizator DavidLDavid Lauran DavidL Data 18 martie 2019 18:21:57
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");

const int NMAX = 1e5 + 5;

int n, m;
vector <int> G[NMAX];
int p[NMAX], niv[NMAX], sus[NMAX];
vector <int> dob[2 * NMAX];
int nrComp;

void dfsStart(int nod)
{
    sus[nod] = NMAX;

    for (auto v: G[nod])
        if (!niv[v]) // fiu
        {
            niv[v] = niv[nod] + 1;
            p[v] = nod;
            dfsStart(v);
            sus[nod] = min(sus[nod], sus[v]);
        }
        else if (v != p[nod]) // muchie de intoarcere
            sus[nod] = min(sus[nod], niv[v]);
}

void dfs(int nod, int comp)
{
    //if (nod == 7)
        //cout << comp;

    for (auto v: G[nod])
        if (p[v] == nod) // fiu
        {
            if (sus[v] < niv[nod] || (dob[comp].size() == 1 && sus[v] == niv[nod])) // poate merge mai sus; il bagam in componenta asta
            {
                dob[comp].push_back(v);
                dfs(v, comp);
            }
            else // nu poate merge mai sus; incep componenta noua cu tatal si fiul in ea
            {
                nrComp++;
                dob[nrComp].push_back(nod);
                dob[nrComp].push_back(v);

                dfs(v, nrComp);
            }
        }
}

int main()
{
    fi >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        fi >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    niv[1] = 1;
    dfsStart(1);

    /*for (int i = 1; i <= n; i++)
        cout << i << ": " << sus[i] << "\n";*/
        //return 0;

    nrComp = 1;
    dob[1].push_back(1);
    dfs(1, 1);

    fo << nrComp << "\n";
    for (int i = 1; i <= nrComp; i++)
    {
        for (auto x: dob[i])
            fo << x << " ";
        fo << "\n";
    }

    return 0;
}