Cod sursa(job #3040879)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 30 martie 2023 15:50:45
Problema Componente biconexe Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAXN 100005
#define MAXM 200005
#define INFI 1000000
using namespace std;

struct XYZ{
  int x,y;
};

vector <int> graf[MAXN];
vector <int> answ[MAXN];
int visi[MAXN];
int adan[MAXN];
int arti[MAXN];
int mini[MAXN];
int t,poz;

void AddEdge(XYZ a){
  graf[a.x].push_back(a.y);
  graf[a.y].push_back(a.x);
}

void DFS(int node,int d,int fath){
  int mi=INFI,c;
  visi[node]=1;
  adan[node]=d;
  mini[node]=d;
  mi=d;
  c=0;
  for(int neigh : graf[node]){
    if(visi[neigh]==0){
      DFS(neigh,d+1,node);
      if(mi>mini[neigh] && neigh!=fath){
        mi=mini[neigh];
      }
      c++;
    }
  }
  if(mi>=d && c>0){
    arti[node]=1;
    t++;
  }
  mi=d;
  for(int neigh : graf[node]){
    if(mi>mini[neigh] && neigh!=fath){
      mi=mini[neigh];
    }
  }
  mini[node]=mi;
}

void DFS2(int node,int i){
  answ[i].push_back(node);
  visi[node]=1;
  for(int neigh : graf[node]){
    if(visi[neigh]==0){
      if(arti[neigh]==1){
        if(arti[node]==0){
          answ[i].push_back(neigh);
        }else{
          poz++;
          answ[poz].push_back(node);
          answ[poz].push_back(neigh);
        }
        poz++;
        DFS2(neigh,poz);
      }else{
        DFS2(neigh,i);
      }
    }
  }
}

int main(){
  int n,m,i,x,y;
  FILE *fin,*fout;
  fin=fopen("biconex.in","r");
  fout=fopen("biconex.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d",&x,&y);
    AddEdge({x,y});
  }

  t=1;
  DFS(1,1,-1);

  fprintf(fout,"%d\n",t);

  for(i=1;i<=n;i++){
    visi[i]=0;
  }

  poz=0;
  DFS2(1,0);

  for(i=0;i<t;i++){
    for(int r:answ[i]){
      fprintf(fout,"%d ",r);
    }
    fprintf(fout,"\n");
  }

  fclose(fin);
  fclose(fout);
  return 0;
}