Cod sursa(job #2376690)

Utilizator PaulRPFRebenciuc Paul-Florin PaulRPF Data 8 martie 2019 17:07:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define Nmax 100002
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr,a,b;
vector<int>v[Nmax],sol[Nmax];
bool viz[Nmax];
int niv[Nmax],low[Nmax];
deque<int>d;

void dfs(int dad,int nod)
{
    viz[nod]=1;
    low[nod]=niv[nod];
    d.push_back(nod);
    for(unsigned i=0;i<v[nod].size();i++)
    {
        int vecin=v[nod][i];
        if(vecin==dad)continue;
        if(viz[vecin])
        {
            low[nod]=min(low[nod],niv[vecin]);
            continue;
        }
        niv[vecin]=niv[nod]+1;
        dfs(nod,vecin);
        low[nod]=min(low[nod],low[vecin]);
        if(low[vecin]>=niv[nod])
        {
            nr++;
            int lst;
            do{
                sol[nr].push_back(d.back());
                lst=d.back();
                d.pop_back();
            }while(!d.empty() and lst!=vecin);
            sol[nr].push_back(nod);
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(0,1);
    g<<nr<<"\n";
    for(int i=1;i<=nr;g<<"\n",i++)
    for(unsigned j=0;j<sol[i].size();j++)
        g<<sol[i][j]<<" ";
    return 0;
}