Cod sursa(job #2686248)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 18 decembrie 2020 19:01:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int dim=1e5+10;
typedef long long ll;
typedef pair<int,int> pi;
int t,T,nvl[dim],low[dim],cnt,N,M,a,b;

stack < int > S;
vector < int >V[dim],viz(dim,0),A[dim];

int DFS(int nod,int niv)
{
    viz[nod]=1;
    nvl[nod]=niv;
    low[nod]=niv;
    S.push(nod);
    for(unsigned int vecin:V[nod])
    {
        if(!viz[vecin])
        {
            DFS(vecin,niv+1);
            low[nod]=min(low[vecin],low[nod]);
            if(low[vecin]>=nvl[nod])
            {
                cnt++;
                while(S.top()!=vecin)
                {
                    A[cnt].pb(S.top());
                    S.pop();
                }
                A[cnt].pb(S.top());
                S.pop();
                A[cnt].pb(nod);
            }
        }
        else
        low[nod]=min(low[nod],nvl[vecin]);
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    DFS(1,1);

    g<<cnt;
    for(int i=1;i<=cnt;i++)
    {
        g<<'\n';
        for(unsigned int j=0;j<A[i].size();j++) g<<A[i][j]<<' ';
    }

    return 0;
}