Cod sursa(job #2195497)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 16 aprilie 2018 15:53:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
vector<int> vec[N];
vector<int> vec2[N];
vector<int> afis[N];
int viz1[N],viz2[N],sortattop[N];
int t;
int ntc;
int n;
void dfs1(int x){
  viz1[x]=true;
  int a;
  for(int i=0;i<vec[x].size();i++){
    a=vec[x][i];
    if(viz1[a]==false){
      dfs1(a);
    }
  }
  t++;
  sortattop[n+1-t]=x;
}
void dfs2(int x){
  viz2[x]=true;
  afis[ntc].push_back(x);
  int a;
  for(int i=0;i<vec2[x].size();i++){
    a=vec2[x][i];
    if(viz2[a]==false){
      dfs2(a);
    }
  }
}
int main()
{
    FILE*fin,*fout;
    int m;
    fin=fopen("ctc.in","r");
    fout=fopen("ctc.out","w");
    int i,j,x1,x2;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
      fscanf(fin,"%d%d",&x1,&x2);
      vec[x1].push_back(x2);
      vec2[x2].push_back(x1);
    }
    for(i=1;i<=n;i++){
      if(viz1[i]==false)
        dfs1(i);
    }
    for(i=1;i<=n;i++){
      if(viz2[sortattop[i]]==false){
        ntc++;
        dfs2(sortattop[i]);
      }
    }
    fprintf(fout,"%d",ntc);
    for(i=1;i<=ntc;i++){
      for(j=0;j<afis[i].size();j++){
        fprintf(fout,"%d ",afis[i][j]);
      }
      fprintf(fout,"\n");
    }
    return 0;
}