Cod sursa(job #2193779)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 11 aprilie 2018 15:29:08
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include<cstdio>
using namespace std;
int vf[200005];
int urm[200005];
int lst[100005];
bool viz[100005];
int nr;
void adauga(int x,int y){
  nr++;
  vf[nr]=y;
  urm[nr]=lst[x];
  lst[y]=nr;
}
void dfs(int x){
  viz[x]=true;
  int p,y;
  p=lst[x];
  while(p!=0){
    y=vf[p];
    if(!viz[y]){
      dfs(y);
    }
    p=urm[p];
  }
}
int main()
{
    FILE*fin,*fout;
    fin=fopen("dfs.in","r");
    fout=fopen("dfs.out","w");
    int x,y,n,m,i,comp=0;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
      fscanf(fin,"%d%d",&x,&y);
      adauga(x,y);
      adauga(y,x);
    }
    for(i=1;i<=n;i++){
      if(viz[i]==false){
        comp++;
        dfs(i);
      }
    }
    fprintf(fout,"%d",comp);
    return 0;
}