Cod sursa(job #2927703)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 21 octombrie 2022 09:26:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAXN 100005
using namespace std;

struct XY{
  int x,y;
};

vector <int> g[MAXN];
vector <int> revg[MAXN];
vector <int> comp[MAXN];
vector <int> ord;
bool mark[MAXN];

void AddMuchie(XY a){
  g[a.x].push_back(a.y);
  revg[a.y].push_back(a.x);
}

void SetMark(){
  int i;
  for(i=0;i<MAXN;i++){
    mark[i]=false;
  }
}

void dfs(vector <int>* graph,vector<int>& visited,int node){
  mark[node]=true;
  for(int neigh : graph[node]){
    if(mark[neigh]==false){
      dfs(graph,visited,neigh);
    }
  }
  visited.push_back(node);
}

int main(){
  int n,m,i,noComp,x;
  XY a;
  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",&a.x,&a.y);
    AddMuchie(a);
  }

  for(i=1;i<=n;i++){
    if(mark[i]==false){
      dfs(g,ord,i);
    }
  }

  SetMark();

  noComp=0;
  while(ord.size()){
    x=ord.back();
    ord.pop_back();
    if(mark[x]==false){
      dfs(revg,comp[noComp],x);
      noComp++;
    }
  }

  fprintf(fout,"%d\n",noComp);
  for(x=0;x<noComp;x++){
    while(comp[x].size()>0){
      fprintf(fout,"%d ",comp[x].back());
      comp[x].pop_back();
    }
    fprintf(fout,"\n");
  }


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