Cod sursa(job #1418953)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 14 aprilie 2015 14:33:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define MAXN 100001

using namespace std;
using Graph = vector<vector<int> >;

ifstream in("dfs.in");
ofstream out("dfs.out");

int N, M;
Graph G(MAXN);
vector<int> visited(MAXN, 0);

void dfs(int source)
{
    visited[source] = 1;
    for (auto &node : G[source])
        if (!visited[node]) 
            dfs(node);
}

int main()
{
    in >> N >> M;

    int x, y;
    for (int i = 1; i <= M; i++) {
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    int connected_components = 0;
    for (int node = 1; node <= N; node++) {
        if (!visited[node]) {
            dfs(node);
            connected_components++;
        }
    }

    out << connected_components << '\n';

    return 0;
}