Pagini recente » Cod sursa (job #594474) | Cod sursa (job #1389705) | Cod sursa (job #1634733) | Cod sursa (job #2001963) | Cod sursa (job #3295380)
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
using namespace std;
class Graph {
public:
unordered_map <int, vector<int> > adj_list;
void add_egde (int n1, int n2) {
adj_list[n1].push_back(n2);
adj_list[n2].push_back(n1);
}
int dfs(int nodes_number) {
vector <int> parents (nodes_number + 1, -1);
vector <int> start_time (nodes_number + 1, 0);
vector <int> end_time (nodes_number + 1, 0);
int comp_conexe = 0;
int timestamp = 0;
for (int i = 1; i <= nodes_number; i++) {
if (parents[i] == -1) {
// cout<< "incep parcurgerea cu nodul: "<< i << '\n';
comp_conexe++;
parents[i] = i;
dfs_recursive(i, parents, start_time, end_time, timestamp);
}
}
// cout<<'\n';
// for (int i = 1; i < start_time.size(); i++) {
// cout<< "Pentru nodul "<< i<< " start : " << start_time[i] << " end: "<< end_time[i] << '\n';
// }
// cout << '\n' << comp_conexe << '\n';
return comp_conexe;
}
void dfs_recursive (int root, vector<int> &parents, vector<int> &start, vector<int> &end, int ×tamp) {
timestamp++;
start[root] = timestamp;
for (auto adj_node : adj_list[root]) {
if (parents[adj_node] == -1) {
parents[adj_node] = root;
dfs_recursive(adj_node, parents, start, end, timestamp);
}
}
timestamp++;
end[root] = timestamp;
}
};
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
Graph g;
int nodes, edges;
fin >> nodes >> edges;
int n1, n2;
while (fin >> n1 && fin >> n2) {
g.add_egde(n1, n2);
// cout<<n1<< " "<<n2<<'\n';
}
fout << g.dfs(nodes);
return 0;
}