Cod sursa(job #1867674)

Utilizator preda.andreiPreda Andrei preda.andrei Data 4 februarie 2017 11:38:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    bool visited = false;
    vector<int> edges;
};

using Graph = vector<Node>;

void Dfs(Graph &g, int node)
{
    g[node].visited = true;
    for (int next : g[node].edges) {
        if (!g[next].visited) {
            Dfs(g, next);
        }
    }
}

int main()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    int n, m;
    fin >> n >> m;

    Graph graph(n);
    while (m--) {
        int x, y;
        fin >> x >> y;
        graph[x - 1].edges.push_back(y - 1);
        graph[y - 1].edges.push_back(x - 1);
    }

    int components = 0;
    for (int i = 0; i < n; ++i) {
        if (!graph[i].visited) {
            ++components;
            Dfs(graph, i);
        }
    }

    fout << components << "\n";
    return 0;
}