Cod sursa(job #3215735)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 15 martie 2024 12:18:26
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define MAXN 100//005
#define MAXM 200//005
#define ALB 0
#define GRI 1
#define BLK 2
using namespace std;

struct XYZ{
  int niv,x;
};

int nod[MAXN];
int nivel[MAXN];
vector <int> graf[MAXN];
vector <int> ans[MAXN];
int fath[MAXN];

int FindFath(int x){
  if(fath[x]==x){
    return x;
  }
  fath[x]=FindFath(fath[x]);
  return fath[x];
}

void Conect(int x,int y){
  int fx,fy;
  fx=FindFath(x);
  fy=FindFath(y);

  if(fx!=fy){
    fath[fx]=fy;
  }
}

XYZ DFS(int node,int adan){
  XYZ aux,r;

  r.niv=adan;
  r.x=node;

  nivel[node]=adan;
  nod[node]=GRI;
  for(int neigh : graf[node]){
    if(nod[neigh]==ALB){
      aux=DFS(neigh,adan+1);
      if(aux.niv<r.niv){
        r=aux;
      }
    }else{
      if(nivel[neigh]<r.niv){
        r.niv=nivel[fath[neigh]];
        r.x=fath[neigh];
      }
    }
  }

  Conect(node,r.x);

  nod[node]=BLK;

  return r;
}

int main(){
  int n,m,i,x,y;
  FILE *fin,*fout;
  fin=fopen("ctc.in","r");
  fout=fopen("ctc.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);
  }

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

  for(i=1;i<=n;i++){
    if(nod[i]==ALB){
      DFS(i,1);
    }
  }

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

  m=0;
  for(i=1;i<=n;i++){
    if(!ans[i].empty()){
      m++;
    }
  }

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

  for(i=1;i<=n;i++){
    if(!ans[i].empty()){
      for(int aux : ans[i]){
        fprintf(fout,"%d ",aux);
      }
      fprintf(fout,"\n");
    }
  }

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