Cod sursa(job #1266391)

Utilizator ml.vladareanVladarean Maria ml.vladarean Data 18 noiembrie 2014 17:57:47
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> nodes [100001];
int visited [100001];

void solve(int node) {
    int noNeighbors = nodes[node].size();
    for (int i = 0; i < noNeighbors; ++ i) {
        if (visited[nodes[node][i]] == 0) {
            visited[nodes[node][i]] = 1;
            solve(nodes[node][i]);
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    vector <int> nodeList;
    int connectedCount = 0;
    freopen("dfs.in", "r", stdin);
    //freopen("dfs.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d", &m);
    
    for (int i = 0; i < m; ++ i) {
        int node, neighbor;
        scanf("%d%d", &node, &neighbor);
        nodes[node].push_back(neighbor);
        nodes[neighbor].push_back(node);
    }
    for (int i = 1; i <= n; ++ i) {
        if (visited[i] == 0) {
            ++ connectedCount;
            visited[i] = 1;
            solve(i);
        }
    }
    printf("%d\n", connectedCount);
    return 0;
}