Cod sursa(job #2196566)

Utilizator AntonescuAlexandruAntonescu Alex AntonescuAlexandru Data 19 aprilie 2018 18:46:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <fstream>
#include <list>
#include <vector>

using namespace std;

#ifndef __GRAPH__H
#define __GRAPH__H


// Structura Node este utila doar pentru implementarea cu liste de vecini
struct Node
{
    std::vector<int> neighbors;
};

class Graph {
private:
    std::vector<Node> nodes; // Implementare cu liste de vecini
    // int **adiacency_matrix;  // Implementare cu matrice de adiacenta

public:
    Graph(int size)
    {
        nodes = vector<Node>(size);
    }

    ~Graph()
    {

    }

    //void add_node(int node);    // Atentie: pentru implementarea cu matrice
    //void remove_node(int node); // puteti ignora aceaste doua functii

    void add_edge(int src, int dst)
    {
        nodes[src].neighbors.push_back(dst);
        nodes[dst].neighbors.push_back(src);
    }
    void remove_edge(int src, int dst)
    {
        int i;
        for (i = 0; i < nodes[src].neighbors.size(); i++)
            if (nodes[src].neighbors[i] == dst)
                nodes[src].neighbors.erase(nodes[src].neighbors.begin() + i);
        for (i = 0; i < nodes[dst].neighbors.size(); i++)
            if (nodes[dst].neighbors[i] == src)
                nodes[dst].neighbors.erase(nodes[dst].neighbors.begin() + i);
    }
    bool has_edge(int src, int dst)
    {
        int i;
        for (i = 0; i < nodes[src].neighbors.size(); i++)
            if (nodes[src].neighbors[i] == dst)
                return true;
        return false;
    }

    std::vector<int> get_neighbors(int node)
    {
        return nodes[node].neighbors;
    }
};

#endif //__GRAPH__H


void dfs(Graph &g, int node, vector<int> &viz)
{
    if(viz[node])
        return;

    viz[node] = 1;
    for (int neigh : g.get_neighbors(node)) {
        if(viz[neigh] == 0){
            dfs(g, neigh, viz);
        }
    }

}

int main()
{
    int m, n, a, b;
    int counter = 0;

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

    f >> n >> m;

    Graph g(n + 1);
    vector<int> viz(n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        f >> a >> b;
        g.add_edge(a, b);
    }

    for (int j = 1; j <= n; j++) {
        if(viz[j] == 0){
            dfs(g, j, viz);
            counter++;
        }
    }

    o << counter;

    f.close();
    o.close();

    return 0;
}