Cod sursa(job #3226925)

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

struct XYZ{
  int x,y;
};

vector <int> graf[MAXN];
int adan[MAXN];
int seen[MAXN];
int mini[MAXN];
vector <int> ans[MAXN];
stack <int> parc;
int timp,k;

void DFS(int node,int fath){

  mini[node]=timp;
  adan[node]=timp;
  seen[node]=1;
  timp++;
  parc.push(node);
  for(int neigh : graf[node]){
    if(seen[neigh]==0){
      DFS(neigh,node);
      if(mini[node]>mini[neigh]){
        mini[node]=mini[neigh];
      }
      if(mini[neigh]>=adan[node]){
        while(parc.top()!=neigh){
          ans[k].push_back(parc.top());
          parc.pop();
        }
        ans[k].push_back(neigh);
        parc.pop();
        ans[k].push_back(node);
        k++;
      }
    }else{
      if(fath!=neigh && adan[neigh]<adan[node]){
        if(mini[node]>adan[neigh]){
          mini[node]=adan[neigh];
        }
      }
    }
  }
  //parc.pop_back();
}

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);
    graf[x].push_back(y);
    graf[y].push_back(x);
  }

  DFS(1,-1);

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

  for(i=0;i<k;i++){
    for(int node : ans[i]){
      fprintf(fout,"%d ",node);
    }
    fprintf(fout,"\n");
  }

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