Cod sursa(job #1547860)

Utilizator cristid9Cristi D cristid9 Data 9 decembrie 2015 23:41:51
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

static int mark = 0;

struct Graph
{
    vector<vector<int>> adj;
    int N;


    Graph(int nodes)
    {
        for (int i = 0; i < nodes; i++)
        {
            adj.push_back(vector<int>());
        }
        N = nodes;
    }

    void addEdge(int i, int j)
    {
        adj[i].push_back(j);
        adj[j].push_back(i);
    }

    int nodes()
    { return N; }
};

static void explore(Graph& graph, int node, int* components)
{
    if (components[node] != -1)
        return; // Already visited.

    components[node] = mark;

    for (int i : graph.adj[node])
    {
        explore(graph, i, components);
    }
}

int countConnectedComponents(Graph& graph)
{
    int components[graph.nodes()];
    for (int i = 0; i < graph.nodes(); i++)
    {
        components[i] = -1;
    }

    for (int node = 0; node < graph.nodes(); node++)
    {
        if (components[node] != -1)
        {
            ++mark;
            continue;
        }
        explore(graph, node, components);
    }

    return mark;
}

int main()
{
    ifstream in("dfs.in");

    int n, m;

    in >> n;
    in >> m;

    Graph graph(n);

    while (m--)
    {
        int i, j;
        in >> i;
        in >> j;
        graph.addEdge(i, j);
    }

    in.close();

    // Now count connected components.

    ofstream out("dfs.out");
    out << countConnectedComponents(graph)
        << endl;
    out.close();

    return 0;
}