Pagini recente » Cod sursa (job #1917344) | Cod sursa (job #2484808) | Cod sursa (job #362563) | Cod sursa (job #2426844) | Cod sursa (job #2785794)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("dfs.in");
ofstream cout ("dfs.out");
const int kNMax = 1000;
/************************** Matrice de adiacenta ********************/
// int n;
// bool edges[kNMax][kNMax]; // false
// void readGraph() {
// cin >> n; // numarul de noduri
// int m; cin >> m; // numarul de muchii
// for (int i = 0; i < m; i++) {
// int a, b; cin >> a >> b; // capetele muchiei
// a--; b--;
// edges[a][b] = edges[b][a] = true;
// }
// }
// void printGraph() {
// cout << " ";
// for (int i = 0; i < n; i++) {
// cout << i + 1 << " ";
// }
// cout << "\n";
// for (int i = 0; i < n; i++) {
// cout << i + 1 << " ";
// for (int j = 0; j < n; j++) {
// cout << edges[i][j] << " ";
// }
// cout << '\n';
// }
// cout << '\n';
// }
/************************** Liste de adiacenta *********************/
// int n;
// int edges[kNMax][kNMax];
// int grad[kNMax];
// void readGraph() {
// cin >> n; // numarul de noduri
// int m; cin >> m; // numarul de muchii
// for (int i = 0; i < m; i++) {
// int a, b; cin >> a >> b; // capetele muchiei
// a--; b--;
// edges[a][grad[a]] = b;
// grad[a]++;
// edges[b][grad[b]] = a;
// grad[b]++;
// }
// }
// void printGraph() {
// for (int i = 0; i < n; i++) {
// cout << i + 1 << ": ";
// for (int j = 0; j < grad[i]; j++) {
// cout << edges[i][j] + 1 << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// }
/*********************** Vectori (stl) de adiacenta *********************/
vector<vector<int>> edges;
vector<bool> viz;
void readGraph() {
int n; cin >> n; // numarul de noduri
int m; cin >> m; // numarul de muchii
edges.resize(n);
viz.resize(n);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b; // capetele muchiei
a--; b--;
edges[a].push_back(b);
edges[b].push_back(a);
}
}
void printGraph() {
// for (auto node : edges) {
// for (auto next : node) {
// cout << node << " " << next << "\n";
// }
// }
for (int i = 0; i < edges.size(); i++) {
cout << i + 1 << ": ";
for (int j = 0; j < edges[i].size(); j++) {
cout << edges[i][j] + 1 << " ";
}
cout << "\n";
}
cout << "\n";
}
// dfs(root)
void dfs(int node) {
// Var 1
// if (viz[node]) { return; }
viz[node] = true;
// for (int i = 0; i < edges[node].size(); i++) {
// int next = edges[node][i];
for (auto next : edges[node]) {
// Var 2
if (viz[next] == false) {
// cout << node + 1 << " -> " << next + 1 << "\n";
dfs(next);
}
}
}
int main() {
readGraph();
// printGraph();
// dfs(0);
// n = edges.size();
int count_con = 0;
for (int i = 0; i < edges.size(); i++) {
if (viz[i] == false) {
count_con++;
// cout << count_con << ":\n";
dfs(i);
// cout << "\n";
}
}
cout << count_con << '\n';
return 0;
}