Cod sursa(job #2503821)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 3 decembrie 2019 20:07:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

const int nmax=100005;

vector<int> G[nmax];
stack<pair<int,int>>Q;

vector<vector<int> >sol;

int low[nmax],dt[nmax],fath[nmax];

bool viz[nmax];

int n,m,a,b;

void comp(int node,int x)
{
   vector<int>q;
   int fx,fy;
   fx=Q.top().first;
   fy=Q.top().second;
   Q.pop();

   q.push_back(fx);q.push_back(fy);

   while(fx!=node || fy!=x)
   {
     fx=Q.top().first;
     fy=Q.top().second;
     Q.pop();

     q.push_back(fx);q.push_back(fy);

   }
   sol.push_back(q);
}

void DFS(int node,int t)
{
   viz[node]=1;
   dt[node]=low[node]=t;

   for(auto x: G[node])
   {
       if(!viz[x])
       {
           fath[x]=node;
           Q.push({node,x});
           DFS(x,t+1);

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

           if(low[x]>=dt[node])
           {
               comp(node,x);
           }

       }
       else if(x!=fath[node])
       {
           low[node]=min(low[node],dt[x]);
       }
   }

}

int main()
{

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    DFS(1,0);

    g<<sol.size()<<"\n";
    for(int i=0;i<sol.size();i++)
    {
        sort(sol[i].begin(),sol[i].end());
        sol[i].erase(unique(sol[i].begin(),sol[i].end()),sol[i].end());
        for(auto x:sol[i])
           g<<x<<" ";
        g<<"\n";
    }
    return 0;
}