Cod sursa(job #3148356)

Utilizator emcerchezEmanuela Cerchez emcerchez Data 31 august 2023 12:16:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.86 kb
#include <bits/stdc++.h>
#define NMAX 100100
#define MMAX 200100
using namespace std;

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

int n;       //numarul de varfuri din graf
int start=1; //varful de start in parcurgerea DFS
int num;     //numarul de ordine al varfului curent in parcurgerea DFS
int nrfii;   //numarul de fii ai varfului de start
int nr;      //numarul de componente biconexe

vector<int> G[NMAX]; //reprezentarea grafului prin liste de adiacenta
int dfn[NMAX], low[NMAX];
bool Art[NMAX]; //vectorul caracteristic al multimii punctelor de articulatie

struct Muchie {int f,  t;};
stack<Muchie> S;
vector<int> B[MMAX]; //componentele biconexe
void Citire();
void Biconex(int ,int );
void Initializare();
void Comp_Biconexa(int, int);
void Scrie(int);

int main()
{int i;
 Citire();
 Initializare();
 Biconex(start,-1);
 //Afisez punctele de articulatie
 fout<<nr<<'\n';
 for (i=1; i<=nr; i++)
     Scrie(i);
 return 0;
}

void Citire()
{int x, y, m, i;
 fin>>n>>m;
 for (i=0; i<m; i++)
     {fin>>x>>y;
      G[x].push_back(y);
      G[y].push_back(x);
     }
}

void Initializare()
{int i;
 for (i=1; i<=n; i++) dfn[i]=low[i]=-1;
 Muchie fictiv={start, -1};
 S.push(fictiv);
}

void Biconex(int u, int tu)
//u este nodul curent; tu este nodul parinte al lui u
{int x, p;
 Muchie m;
 dfn[u]=low[u]=++num;
 //parcurg lista de adiacenta G nodului u
 for (p=0; p<G[u].size(); p++)
      {x=G[u][p];  //x este un nod adiacent cu u
       if (x!=tu && dfn[x]<dfn[u])
          //insereaza in stiva S muchia [u,x]
	     {m.f=x; m.t=u; S.push(m); }
       if (dfn[x]==-1) //x nu G mai fost vizitat
          {if (u==start) //am gasit un fiu al varfului start
              nrfii++;
           Biconex(x,u);
           low[u]=min(low[u],low[x]);
	       if (low[x]>=dfn[u]) //u este punct de articulatie
              //am identificat o componenta biconexa,
              //formata din muchiile din stiva S pana la
              //intalnirea muchiei [u,x]
              { if (u!=start) Art[u]=1;
                 Comp_Biconexa(x, u); }
          }
         else //x a mai fost vizitat
         if (x!=tu)
            //x nu este tatal lui u,
            //deci [u,x] e muchie de intoarcere la u la x
            low[u]=min(low[u],dfn[x]);
      }
}

void Comp_Biconexa(int x, int u)
//afiseaza componenta biconexa G muchiei [x,u]
{Muchie p;
 nr++;      //incrementez numarul de componente Biconexe
 do
   {p=S.top(); S.pop(); //extrag o muchie din stiva
    B[nr].push_back(p.f);
    B[nr].push_back(p.t);
   }
 while (p.t!=u || p.f!=x);
}

void Scrie(int i)
//afisam varfurile din componenta biconexa i
{int j, prec;
 sort(B[i].begin(), B[i].end());
 fout<<B[i][0];
 prec=B[i][0];
 for (j=1; j<B[i].size(); j++)
      if (B[i][j]!= prec)
         {fout<<' '<<B[i][j]; prec=B[i][j];}
 fout<<'\n';
}