Cod sursa(job #2021326)

Utilizator StefanManolacheManolache Stefan StefanManolache Data 13 septembrie 2017 11:47:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <vector>

FILE *fin = fopen("dfs.in", "r");
FILE *fout = fopen("dfs.out", "w");

#define maxn 100000





std::vector<int> v[maxn + 1];

int viz[maxn + 1];

void dfs(int t) {
    viz[t] = 1;
    for (auto y : v[t])
        if(viz[y] != 1)
            dfs(y);
}



int main()
{

    int n, m, x, y, rez = 0;

    fscanf(fin, "%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        fscanf(fin, "%d%d", &x, &y);
        v[x].push_back (y);
        v[y].push_back (x);
    }
    for (int i = 1; i <= n; i++)
        if (viz[i] != 1) {
            dfs(i);
            rez++;
        }
    fprintf(fout, "%d", rez);
    return 0;
}