Cod sursa(job #3226886)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 23 aprilie 2024 10:58:13
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define MAXN 100005
using namespace std;

struct XYZ{
  int x,y;
};

vector <int> graf[MAXN];
int adan[MAXN];
int jump[MAXN];
int fath[MAXN];
vector <int> vf[MAXN];
XYZ ans[MAXN];
int k;

int GetFath(int node){
  if(fath[node]==node){
    return node;
  }
  fath[node]=GetFath(fath[node]);
  return fath[node];
}

void Conect(int a,int b){
  int fa,fb;

  fa=GetFath(a);
  fb=GetFath(b);

  fath[fa]=fb;
}

void DFS(int node,int jos,int fath){
  int sarit;

  jump[node]=jos;
  adan[node]=jos;
  sarit=jos;
  for(int neigh : graf[node]){
    if(neigh!=fath){
      if(adan[neigh]==0){
        DFS(neigh,jos+1,node);
      }
      sarit=min(sarit,jump[neigh]);
      if(jump[neigh]<=adan[node]){
        Conect(neigh,node);
      }else{
        if(node<neigh){
          ans[k]={node,neigh};
          k++;
        }
      }
    }
  }

  jump[node]=sarit;
}

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

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

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d",&x,&y);
    graf[x].push_back(y);
    graf[y].push_back(x);
  }

  DFS(1,1,-1);

  for(i=1;i<=n;i++){
    vf[GetFath(i)].push_back(i);
  }

  c=0;
  for(i=1;i<=n;i++){
    if(vf[i].size()>1){
      c++;
    }
  }

  fprintf(fout,"%d\n",c+k);

  for(i=1;i<=n;i++){
    if(vf[i].size()>1){
      for(int node : vf[i]){
        fprintf(fout,"%d ",node);
      }
      fprintf(fout,"\n");
    }
  }
  for(i=0;i<k;i++){
    fprintf(fout,"%d %d\n",ans[i].x,ans[i].y);
  }

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