Cod sursa(job #2576287)

Utilizator DavidDragulinDragulin David DavidDragulin Data 6 martie 2020 18:20:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int N=100009;
int lvl[N],low[N],n,m,h,k;
vector <int> v[N],sol[N];
stack <int> sk;
void dfs(int nod)
{
    h++;
    sk.push(nod);
    for(auto it:v[nod])
    {
        if(!lvl[it])
        {
            int x=h;
            lvl[it]=low[it]=lvl[nod]+1;
            dfs(it);
            low[nod]=min(low[nod],low[it]);
            if(low[it]>=lvl[nod])
            {
                sol[++k].pb(nod);
                while(h>x)
                {
                    h--;
                    sol[k].pb(sk.top());
                    sk.pop();
                }
            }
        }
        low[nod]=min(low[nod],lvl[it]);
    }
}
int main()
{
    fin.sync_with_stdio(false);
    fin.tie(0);
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    lvl[1]=low[1]=1;
    dfs(1);
    fout<<k<<" "<<'\n';
    for(int i=1;i<=k;i++)
    {
        for(auto it:sol[i])
            fout<<it<<" ";
        fout<<'\n';
    }
    return 0;
}