Cod sursa(job #2576812)

Utilizator andra1782Andra Alazaroaie andra1782 Data 6 martie 2020 23:15:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 100001
FILE *fin,*fout;
char viz[MAX];
int niv[MAX],nivmin[MAX],cb;
std::vector<int>l[MAX];
std::vector<int>r[MAX];
std::stack<int>s;

void dfs(int nod, int p){
  viz[nod]=1;
  niv[nod]=niv[p]+1;
  nivmin[nod]=niv[nod];
  s.push(nod);
  for(auto i: l[nod])
    if(i!=p)
      if(!viz[i]){
        dfs(i,nod);
        nivmin[nod]=nivmin[nod]<nivmin[i] ? nivmin[nod]:nivmin[i];//nivmin-urile fiilor
        if(niv[nod]<=nivmin[i]){//nod de articulatie daca nu e radacina
          int f=s.top();
          s.pop();
          while(f!=i){
            r[cb].push_back(f);
            f=s.top();
            s.pop();
          }
          r[cb].push_back(i);
          r[cb++].push_back(nod);
        }
      }else
        nivmin[nod]=nivmin[nod]<niv[i] ? nivmin[nod]:niv[i];//niv muchie de intoarcere
}

int main(){
  fin=fopen("biconex.in","r");
  fout=fopen("biconex.out","w");
  int n,m,i,x,y;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++){
    fscanf(fin,"%d%d",&x,&y);
    l[x].push_back(y);
    l[y].push_back(x);
  }
  dfs(1,0);
  fprintf(fout,"%d\n",cb);
  for(i=0; i<cb; i++){
    for(auto a: r[i])
      fprintf(fout,"%d ",a);
    fprintf(fout,"\n");
  }
  fclose(fin);
  fclose(fout);
  return 0;
}