Cod sursa(job #1740337)

Utilizator AplayLazar Laurentiu Aplay Data 11 august 2016 14:30:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

#define NMAX 100001

#define pb push_back

using namespace std;

int N, M, visited[NMAX], x, y, answer;
vector<int> graph[NMAX];

void dfs(int node) {
    for (vector<int>::iterator it = graph[node].begin(); it < graph[node].end(); ++it) {
        if (!visited[*it]) {
            visited[*it] = 1;
            dfs(*it);
        }
    }
}

int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d%d", &N, &M);
    for (int it = 0; it < M; ++it) {
        scanf("%d%d", &x, &y);
        graph[x].pb(y);
        graph[y].pb(x);
    }

    for (int it = 1; it <= N; ++it) {
        if (!visited[it]) {
            visited[it] = 1;
            ++answer;
            dfs(it);
        }
    }

    printf("%d", answer);

    fclose(stdin);
    fclose(stdout);
    return 0;
}