Cod sursa(job #3040508)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 29 martie 2023 22:40:52
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAXN 100005
#define MAXM 100005
using namespace std;

struct XYZ{
  int x,y;
};

vector <int> graf[MAXM];
vector <int> ginv[MAXM];
vector <int> parc;
vector <int> ans[MAXN];
int visited[MAXN];

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

void DFS(vector <int> *graful,vector <int> &parcurs, int node){

  visited[node]=1;
  for(int neigh : graful[node]){
    if(visited[neigh]==0){
      DFS(graful,parcurs,neigh);
    }
  }
  parcurs.push_back(node);
}

int main(){
  int n,m,i,x,y,r;
  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);
    ginv[y].push_back(x);
  }

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

  for(i=1;i<=n;i++){
    if(visited[i]==0){
      DFS(graf,parc,i);
    }
  }

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

  r=0;
  for(int node : parc){
    if(visited[node]==0){
      DFS(graf,ans[r],node);
      r++;
    }
  }

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

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