Cod sursa(job #2405921)

Utilizator onipreponiprep oniprep Data 15 aprilie 2019 10:26:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int N=100009;
int n,m,h,k;
int lvl[N],low[N];
vector <int> v[N],sol[N];
stack <int> sk;
void dfs(int nod)
{
    sk.push(nod);
    h++;
    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].push_back(nod);
                while(h>x)
                {
                    h--;
                    sol[k].push_back(sk.top());
                    sk.pop();
                }
            }
        }
        low[nod]=min(low[nod],lvl[it]);
    }
}
int main()
{
    fin.sync_with_stdio(false);
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    lvl[1]=low[1]=1;
    dfs(1);
    fout<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<sol[i].size();j++)
            fout<<sol[i][j]<<" ";
        fout<<'\n';
    }
    return 0;
}