Cod sursa(job #3252406)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 29 octombrie 2024 15:43:37
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 3.19 kb
#include <bits/stdc++.h>

using namespace std;

class Graph {
private:
    // lista de adiacenta
    // neighbours[3] = {4, 5} are semnificatia ca vecinii lui 3 sunt 4 si 5
    vector<vector<int>> neighbours;

    // matrice de adiacenta
    // edge[3][5] = true are semnificatia ca exista muchie de la 3 la 5
    vector<vector<bool>> edge;

    // lista de muchii
    // edge_list[3] este a treia muchie din lista
    // edge_list[3].first este nodul de la care pleaca muchia 3
    // edge_list[3].second este nodul la care ajunge muchia 3
    vector<pair<int, int>> edge_list;

    size_t no_of_nodes;
    size_t no_of_edges;
    bool is_directed = false;

    void dfs(int start, vector<int> &color, int color_to_use);
    void dfs(int start, int &current_time, vector<int> &discover_time, vector<int> &finish_time, vector<int> &level, vector<int> &father);

public:
    void read_from_file(const string &file_name, bool read_direction = false);
    void dfs(int start, vector<bool> &visited, bool print = false);
    int get_connected_components_count();
};


void Graph::read_from_file(const string &file_name, bool read_direction) {
    ifstream fin(file_name);

    fin >> no_of_nodes >> no_of_edges;
    neighbours.resize(no_of_nodes);
    edge.resize(no_of_nodes, vector<bool>(no_of_nodes, false));

    if (read_direction) {
        fin >> is_directed;
    }

    for (int i = 0; i < no_of_edges; ++i) {
        int node1, node2;
        fin >> node1 >> node2;

        --node1, --node2;
        edge[node1][node2] = true;
        edge[node2][node1] = !is_directed || edge[node2][node1];

        neighbours[node1].push_back(node2);
        if (!is_directed) neighbours[node2].push_back(node1);

        edge_list.push_back({node1, node2});
    }
}

void Graph::dfs(int start, vector<bool> &visited, bool print) {
    visited[start] = true;
    if (print) cout << start << " ";

    for (auto neighbour : neighbours[start]) {
        if (!visited[neighbour]) {
            dfs(neighbour, visited, print);
        }
    }
}

void Graph::dfs(int start, vector<int> &color, int color_to_use) {
    color[start] = color_to_use;
    for (auto neighbour : neighbours[start]) {
        if (!color[neighbour]) {
            dfs(neighbour, color, color_to_use);
        }
    }
}

int Graph::get_connected_components_count() {
    int connected_components_count = 0;
    vector<int> color(no_of_nodes);

    for (int node = 0; node < no_of_nodes; ++node) {
        if (!color[node]) {
            dfs(node, color, ++connected_components_count);
        }
    }

    return connected_components_count;
}

void Graph::dfs(int start, int &current_time, vector<int> &discover_time, vector<int> &finish_time, vector<int> &level, vector<int> &father) {
    discover_time[start] = ++current_time;

    for (auto neighbour : neighbours[start]) {
        if (!discover_time[neighbour]) {
            father[neighbour] = start;
            level[neighbour] = level[start] + 1;

            dfs(neighbour, current_time, discover_time, finish_time, level, father);
        }
    }

    finish_time[start] = ++current_time;
}


int main()
{
    Graph g;
    g.read_from_file("dfs.in");

    ofstream fout("dfs.out");
    fout << g.get_connected_components_count();

    return 0;
}