Cod sursa(job #2722254)

Utilizator PulpysimusJurjiu Tandrau Darius Stefan Pulpysimus Data 12 martie 2021 18:10:28
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,disc[100001],low[100001],t,nr;
bool viz[100001];
stack < pair <int,int> >  S;

vector <int > G[100001];
void read()
{
    f>>n>>m;
int a,b;
for(int i=1;i<=m;i++)
{
    f>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
}
}
void DFS(int node,int parent)
{
    int son;
S.push({parent,node});
    viz[node]=1;
    disc[node]=low[node]=++t;
    for(auto x:G[node])
    {
       if(!viz[x])
           {
               DFS(x,node);son=x;

           }
       if(x!=parent)
       {
           low[node]=min(low[node],low[x]);
       }
      if(x==son && low[x]>=disc[node]) {
            nr++;
while(!S.empty() && S.top().second!=node) {g<<S.top().second<<" ";S.pop();}
g<<S.top().second<<"\n";

    }
    }

}

int main()
{
    read();
    DFS(1,0);


}