Cod sursa(job #1925621)

Utilizator Mstar_AngelComan Mara Stefania Mstar_Angel Data 13 martie 2017 14:39:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
#include<vector>
#define N 100001
using namespace std;
vector <int> v[N];
bool viz[N];

void dfs (int nod){
  int i;
  viz[nod] = 1;
  for (i=0;i<v[nod].size();i++)
    if (viz[v[nod][i]] == 0)
      dfs (v[nod][i]);
}

int main (){
  FILE *in,*out;
  in = fopen ("dfs.in","r");
  out = fopen ("dfs.out","w");
  int n,m,i,n1,n2,cate;
  fscanf(in,"%d%d",&n,&m);
  for (i=1;i<=m;i++){
    fscanf(in,"%d%d",&n1,&n2);
    v[n1].push_back(n2);
    v[n2].push_back(n1);
  }

  cate = 0;
  for (i=1;i<=n;i++)
    if (viz[i] == 0){
      cate ++;
      dfs (i);
    }

  fprintf (out,"%d",cate);


  fclose (in);
  fclose (out);
  return 0;
}