Cod sursa(job #2722344)

Utilizator PulpysimusJurjiu Tandrau Darius Stefan Pulpysimus Data 12 martie 2021 19:24:52
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 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],wentonce;
stack < 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)
{
S.push(node);
    viz[node]=1;
    disc[node]=low[node]=++t;
    for(auto x:G[node])
    {
       if(!viz[x])
           {
              wentonce=true; DFS(x,node);


           low[node]=min(low[node],low[x]);
               if(low[x]>=disc[node]) {
            nr++;
while(S.top() != x)
                    {
                        C[nr].push_back(S.top());
                        S.pop();
                    }
                    S.pop();
                    C[nr].push_back(node);
                    C[nr].push_back(x);


    }
       }
       else    low[node]=min(low[node],low[x]);

    }

}

int main()
{
    read();


    for (int i = 1; i <= n; i++)  {
		if (!viz[i]) {
                wentonce=false;
			DFS(i,0);
        if(!wentonce) {C[++nr].push_back(i);}
		}
    }    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";
    }


}