Pagini recente » Cod sursa (job #1848570) | Cod sursa (job #710570) | Cod sursa (job #2232372) | Cod sursa (job #1739656) | Cod sursa (job #3252406)
#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 ¤t_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 ¤t_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;
}