Cod sursa(job #1012908)

Utilizator sziliMandici Szilard szili Data 19 octombrie 2013 20:38:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

vector<int> adjacencyList[100001];
int visited[100001];

void dfs(int node){
    visited[node] = 1;

    for (int i=0; i<adjacencyList[node].size(); i++){
        int newNode = adjacencyList[node][i];

        if (!visited[newNode]){
            dfs(newNode);
        }
    }

}

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

    int n,m;
    scanf("%d %d", &n, &m);

    for (int i=0; i<m; i++){
        int from,to;
        scanf("%d %d", &from, &to);

        adjacencyList[from].push_back(to);
        adjacencyList[to].push_back(from);
    }

    int number = 0;

    for (int i=1; i<=n; i++){
        if (!visited[i]){
            dfs(i);
            number++;
        }

    }

    printf("%d", number);

    return 0;
}