Cod sursa(job #2575596)

Utilizator andra1782Andra Alazaroaie andra1782 Data 6 martie 2020 14:35:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define MAX 100001
FILE *fin,*fout;
int ctc;
char viz[MAX],vizt[MAX];
std::vector<int>l[MAX];
std::vector<int>lt[MAX];
std::stack<int>s;
std::vector<int>r[MAX];

void dfs(int nod){
  viz[nod]=1;
  for(auto i: l[nod])
    if(!viz[i])
      dfs(i);
  s.push(nod);
}

void dfst(int nod){
  vizt[nod]=1;
  r[ctc].push_back(nod);
  for(auto i: lt[nod])
    if(!vizt[i])
      dfst(i);
}

int main(){
  fin=fopen("ctc.in","r");
  fout=fopen("ctc.out","w");
  int n,m,i,x,y;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++){
    fscanf(fin,"%d%d",&x,&y);
    l[x].push_back(y);
    lt[y].push_back(x);
  }
  for(i=1; i<=n; i++)
    if(!viz[i])
      dfs(i);
  while(!s.empty()){
    int f=s.top();
    s.pop();
    if(!vizt[f]){
      dfst(f);
      ctc++;
    }
  }
  fprintf(fout,"%d\n",ctc);
  for(i=0; i<ctc; i++){
    for(auto a: r[i])
      fprintf(fout,"%d ",a);
    fprintf(fout,"\n");
  }
  fclose(fin);
  fclose(fout);
  return 0;
}