Cod sursa(job #1817500)

Utilizator mihai.alphamihai craciun mihai.alpha Data 27 noiembrie 2016 22:20:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <vector>
using namespace std;

vector <int> v[100001];
int folosit[100001];

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


int main()  {
    FILE *fin, *fout;
    fin = fopen("dfs.in", "r");
    fout = fopen("dfs.out", "w");
    int n, m;
    fscanf(fin, "%d%d", &n, &m);
    int i;
    for(i = 0;i < m;i++)  {
        int auxx, auxy;
        fscanf(fin, "%d%d", &auxx, &auxy);
        v[auxx].push_back(auxy);
        v[auxy].push_back(auxx);
    }
    int comp = 0;
    for(i = 1;i <= n;i++)
    if(folosit[i] == 0)  {
        dfs(i);
        comp++;
    }
    fprintf(fout, "%d", comp);
    fclose(fin);
    fclose(fout);
    return 0;
}