Cod sursa(job #2565844)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 2 martie 2020 17:11:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define Dim 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,low[Dim],nvl[Dim],a,b,cnt;
int viz[Dim];

vector < int > V[Dim],A[Dim];
stack < int > S;

void DFS(int nod,int niv)
{
   viz[nod]=1;
   nvl[nod]=niv;
   low[nod]=niv;
   S.push(nod);

   for(unsigned int i=0;i<V[nod].size();i++)
   {
       int vecin=V[nod][i];

       if( viz[vecin] == 1 ) low[nod]=min(low[nod],nvl[vecin]);
       else
       if( viz[vecin] == 0 )
       {
           DFS(vecin,niv+1);
           low[nod]=min(low[nod],low[vecin]);

           if( low[vecin] >= nvl[nod] )
           {
               cnt++;
               while( S.top() != vecin )
               {
                   A[cnt].push_back(S.top());
                   S.pop();
               }
               A[cnt].push_back(vecin);
               S.pop();
               A[cnt].push_back(nod);
           }
       }

   }
   viz[nod]=2;
}

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(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;
}