Pagini recente » Cod sursa (job #794096) | Cod sursa (job #1115262) | Cod sursa (job #3152039) | Cod sursa (job #231783) | Cod sursa (job #2641898)
#include <iostream>
#include <fstream>
const int Nodes = 100005;
bool Visited[Nodes];
int count;
struct Node {
int index;
struct Node* next;
};
struct Node* N[Nodes];
void addAdjacentNode(Node*& header, int i) {
Node* iterator = header;
while (iterator->next != NULL)
iterator = iterator->next;
Node* added = new Node;
added->index = i;
added->next = NULL;
iterator->next = added;
return;
}
void DFS(int index) {
if (Visited[index]) return;
Visited[index] = true;
Node* iterator = N[index];
while (iterator->next != NULL) {
iterator = iterator->next;
DFS(iterator->index);
}
return;
}
int main() {
std::ifstream fin("DFS.in");
std::ofstream fout("DFS.out");
int nodes{}, edges{}, i{};
fin >> nodes >> edges;
for (i = 1; i <= nodes; i++) {
N[i] = new Node;
N[i]->index = i;
N[i]->next = NULL;
}
while (edges--) {
int x{}, y{};
fin >> x >> y;
addAdjacentNode(N[x], y);
addAdjacentNode(N[y], x);
}
for (i = 1; i <= nodes; i++) {
if (!Visited[i]) {
DFS(i);
count++;
}
}
fout << count << "\n";
fin.close();
fout.close();
return 0;
}