Cod sursa(job #2186614)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 25 martie 2018 19:54:48
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector <int> G[100005];
vector <int> sol[100005];
int niv[100005],best[100005],n,m,nrSol=0;
bool viz[100005];
stack <int> noduri;
void citire()
{
    scanf("%d%d",&n,&m);
    int nod1,nod2;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&nod1,&nod2);
        G[nod1].push_back(nod2);
        G[nod2].push_back(nod1);
    }
}
void dfs(int nod,int tata)
{
    viz[nod]=1;
    noduri.push(nod);
    for(auto fiu:G[nod])
    {
        if(fiu!=tata)
            if(!viz[fiu])
            {
                best[fiu]=niv[fiu]=niv[nod]+1;
                dfs(fiu,nod);
                best[nod]=min(best[nod],best[fiu]);
                if(best[fiu]>=niv[nod])
                {
                    nrSol++;
                    while(noduri.top()!=nod)
                    {
                        sol[nrSol].push_back(noduri.top());
                        noduri.pop();
                    }
                    sol[nrSol].push_back(noduri.top());
                }
            }
            else
                best[nod]=min(best[nod],niv[fiu]);
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    citire();
    dfs(1,0);
    printf("%d\n",nrSol);
    for(int i=1;i<=nrSol;i++)
    {
        for(auto ii:sol[i])
            printf("%d ",ii);
        printf("\n");
    }
    return 0;
}