Cod sursa(job #1883613)

Utilizator david.sachelarieDavid Sachelarie david.sachelarie Data 18 februarie 2017 09:38:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector <int> v[100001];
char viz[100001];
void dfs(int nod,int n){
    int i;
    viz[nod]=1;
    for(i=0;(unsigned int)i<v[nod].size();i++)
        if(viz[v[nod][i]]!=1)
            dfs(v[nod][i],n);
}
int main()
{
    FILE*fin,*fout;
    int n,suma=0,m,i,a,b;
    fin = fopen("dfs.in" ,"r");
    fout = fopen("dfs.out" ,"w");
    fscanf(fin, "%d%d" ,&n,&m);
    for(i=0;i<m;i++){
        fscanf(fin, "%d%d" ,&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++){
        if(viz[i]!=1){
            suma++;
            dfs(i,n);
        }
    }
    fprintf(fout, "%d\n" ,suma);
    fclose(fin);
    fclose(fout);
    return 0;
}