Cod sursa(job #2928066)

Utilizator albertaizicAizic Albert albertaizic Data 22 octombrie 2022 07:47:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
#define MAX_N 100000

vector<int> graph[MAX_N],revGraph[MAX_N],order,comp[MAX_N];
bool viz[MAX_N];


void dfs(vector<int>* graph,vector<int>& vis, int i){
    viz[i]=true;

    for(int n:graph[i])
      if(!viz[n])
        dfs(graph,vis,n);

    vis.push_back(i);
}

int main(){
    FILE *fin,*fout;
    int n,m,i,a,b,x,nr;
    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,&b);
      graph[a-1].push_back(b-1);
      revGraph[b-1].push_back(a-1);
    }

    for(x=0;x<n;x++)
      if(!viz[x])
        dfs(graph,order,x);

    for(i=0;i<n;i++)
      viz[i]=false;

    nr=0;
    while(order.size()){
      x=order.back();
      order.pop_back();
      if(!viz[x]){
        dfs(revGraph,comp[nr],x);
        nr++;
      }
    }


    fprintf(fout,"%d\n",nr);
    for(i=0;i<nr;i++){
      for(int j:comp[i]){
        fprintf(fout,"%d ",j+1);
      }
      fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}