Cod sursa(job #2186661)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 25 martie 2018 20:29:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 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 <pair<int,int> > muchii;
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;
    for(auto fiu:G[nod])
    {
        if(fiu==tata)
            continue;
        if(!viz[fiu])
        {
            muchii.push({fiu,nod});
            best[fiu]=niv[fiu]=niv[nod]+1;
            dfs(fiu,nod);
            best[nod]=min(best[nod],best[fiu]);
            if(best[fiu]>=niv[nod])
            {
                nrSol++;
                while(muchii.top().second!=nod)
                {
                    sol[nrSol].push_back(muchii.top().first);
                    muchii.pop();
                }
                sol[nrSol].push_back(muchii.top().first);
                sol[nrSol].push_back(muchii.top().second);
                muchii.pop();
            }
        }
        else
            best[nod]=min(best[nod],niv[fiu]);

    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i,0);
    printf("%d\n",nrSol);
    for(int i=1; i<=nrSol; i++)
    {
        for(auto ii:sol[i])
            printf("%d ",ii);
        printf("\n");
    }
    return 0;
}