Cod sursa(job #2356816)

Utilizator cristiangeambasuCristian Geambasu cristiangeambasu Data 26 februarie 2019 22:02:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    bool isVisited;
    vector<int> edges;

    Node() :
        isVisited(false),
        edges()
    {
    }
};

void DFS(vector<Node> &nodes, int currentNode)
{
    nodes[currentNode].isVisited = true;
    for(size_t i = 0; i < nodes[currentNode].edges.size(); i++)
    {
        int v = nodes[currentNode].edges[i];
        if(!nodes[v].isVisited)
        {
            DFS(nodes, v);
        }
    }
}

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

    if(!fin.is_open() || !fout.is_open())
        return 1;

    vector<Node> nodes;
    int n, m, c = 0;
    fin >> n >> m;

    for(int i = 0; i < n; i++)
        nodes.push_back(Node());

    for(int i = 0, x, y; i < m; i++)
    {
        fin >> x >> y;
        nodes[x - 1].edges.push_back(y - 1);
        nodes[y - 1].edges.push_back(x - 1);
    }

    for(int i = 0; i < n; i++)
    {
        if(!nodes[i].isVisited)
        {
            c++;
            DFS(nodes, i);
        }
    }

    fout << c;

    fin.close();
    fout.close();

    return 0;
}