Cod sursa(job #921701)

Utilizator teo29bruh pls teo29 Data 21 martie 2013 11:03:42
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <vector>
#define  max1 100005
#define  max2 200000
#include <stdio.h>

using namespace std;

int viz[max1];


void df(vector<int> v[max1],int x){
 viz[x] = 1;
 for(int i = 1;i <= v[x].size(); ++i)
    if(viz[v[x][i]] == 0) df(v,v[x][i]);

}



int main()
{

    int n,m,i,a,b,k = 0;
    FILE *f,*g;
    f = fopen("dfs.in","r");
    g = fopen("dfs.out","w");

    vector <int> vec[max1];

     fscanf(f,"%d",&n);
     fscanf(f,"%d",&m);
        for( i = 1; i <= m; i++){
          fscanf(f,"%d",&a);
          fscanf(f,"%d",&b);
          vec[a].push_back(b);
          vec[b].push_back(a);
        }
        for (i = 1; i <= n; i++) if (!viz[i]) { k++; df(vec,i);}
        fprintf(g,"%d", k);

return 0;
}