Cod sursa(job #2501351)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 29 noiembrie 2019 16:10:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include<iostream>
#include<stack>
#include<bits/stdc++.h>
using namespace std;

#define NMAX 100005


ifstream fin("biconex.in");
ofstream fout("biconex.out");

int minim(int x,int y)
{
   if(x<y) return x;
   else return y;
}

vector <int> v[NMAX];
int dfs[NMAX],low[NMAX];
int vfs;
int nrdfs;
int nr;
int n,m;
vector<int> solutie[NMAX];
int viz[NMAX];

struct muchie
{
   int f,t;
};

muchie S[NMAX];

void citeste()
{
   fin>>n>>m;
   int x,y;
   for(int i=1;i<=m;i++)
   {
      fin>>x>>y;
      v[x].push_back(y);
      v[y].push_back(x);
   }
   for(int i=1;i<=n;i++)
      dfs[i] = low[i] = -1;
   S[0].f = 1;
   S[0].t = -1;
   vfs=0;
   nrdfs=0;
}

void afisare(int x,int u)
{

   muchie p;
   nr++;
   do
   {
      p = S[vfs--];

      if(viz[p.f] != nr)
      {
         viz[p.f] = nr;
         solutie[nr].push_back(p.f);
      }
      if(viz[p.t] != nr)
      {
         viz[p.t] = nr;
         solutie[nr].push_back(p.t);
      }

   }while(p.f !=x || p.t != u);
}

void biconexe(int u,int tu)
{

   int x,p;
   dfs[u] = low[u] = ++nrdfs;
   for(p = 0 ;p<v[u].size();p++)
   {
      x = v[u][p];
      if(x!=tu && dfs[x] < dfs[u])
      {
         S[++vfs].f = x;
         S[vfs].t = u;
      }
      if(dfs[x] == -1)
      {
         biconexe(x,u);
         low[u] = minim(low[u],low[x]);
         if(low[x] >= dfs[u])
         {
            afisare(x,u);
         }
      }
      else
      {
         low[u] = minim(low[u],dfs[x]);
      }

   }
}

int main()
{
   citeste();
   biconexe(1,-1);
   fout<<nr<<'\n';
   for(int i=1;i<=nr;i++)
   {
      sort(solutie[i].begin(),solutie[i].end());
      for(int j=0;j<solutie[i].size();j++)
         fout<<solutie[i][j]<<" ";
      fout<<'\n';
   }
   return 0;
}