Cod sursa(job #2722275)

Utilizator PulpysimusJurjiu Tandrau Darius Stefan Pulpysimus Data 12 martie 2021 18:24:20
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 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],C[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) {C[nr].push_back(S.top().second);S.pop();}
C[nr].push_back(S.top().second);

    }
    }

}

int main()
{
    read();
    DFS(1,0);
    g<<nr<<"\n";
    for(int i=1;i<=nr;i++)
    {
        sort(C[i].begin(),C[i].end());
        for(auto x:C[i])
            g<<x<<" ";
        g<<"\n";
    }


}