Cod sursa(job #1266345)

Utilizator ml.vladareanVladarean Maria ml.vladarean Data 18 noiembrie 2014 17:11:22
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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(visited[nodes[node][i]]);
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    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);
    }
    for (int i = 1; i <= n; ++ i) {
        if (visited[i] == 0) {
            ++ connectedCount;
            visited[i] = 1;
            solve(i);
        }
    }
    printf("%d\n", connectedCount);
    return 0;
}