Cod sursa(job #2576447)

Utilizator danin01Nastase Daniel danin01 Data 6 martie 2020 19:31:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define inf 1000000001

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

vector<int>v[100001],sol[100001];
int n,m,k,h,low[100001],disc[100001];
stack<int>sk;

void dfs(int nod)
{
    h++;
    sk.push(nod);
    for(int i=0;i<v[nod].size();++i)
    {

        if(!disc[v[nod][i]])
        {

            int crt=h;
            low[v[nod][i]]=disc[v[nod][i]]=disc[nod]+1;
            dfs(v[nod][i]);
            low[nod]=min(low[nod],low[v[nod][i]]);

            if(low[v[nod][i]]>=disc[nod])
            {

                k++;
                sol[k].push_back(nod);
                while(h>crt)
                {

                    h--;
                    sol[k].push_back(sk.top());
                    sk.pop();

                }

            }

        }

        low[nod]=min(low[nod],disc[v[nod][i]]);

    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    disc[1]=low[1]=1;
    dfs(1);
    g<<k<<'\n';

    for(int i=1;i<=k;++i)
    {
        for(auto j=0;j<sol[i].size();++j)
        {
            g<<sol[i][j]<<" ";
        }
        g<<'\n';
    }

    return 0;
}