Cod sursa(job #2478672)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 22 octombrie 2019 15:40:58
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include<queue>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");
int i,a,b,n,m,ok,p;
int low[100010],niv[100010];
vector<int> v[100010],sol[100010],q;
void dfs(int nod,int tata)
{
    q.push_back(nod);
    low[nod]=niv[nod];
    for(auto it:v[nod])
    {
        if(tata==it) continue;
        if(niv[it])
        {
            low[nod]=min(low[nod],niv[it]);
            continue;
        }
        niv[it]=niv[nod]+1;
        dfs(it,nod);
        low[nod]=min(low[it],low[nod]);
        if(niv[nod]<=low[it])
        {
            ok++;
            while(q.back()!=nod)
            {
                sol[ok].push_back(q.back());
                q.pop_back();
            }
            sol[ok].push_back(nod);
        }
    }
}

int main ()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    niv[1]=1;
    dfs(1,0);
    fout<<ok<<"\n";
    for(i=1;i<=ok;i++)
    {
        for(auto it:sol[i])
            fout<<it<<" ";
        fout<<"\n";
    }
    return 0;
}