Pagini recente » Cod sursa (job #1683659) | Cod sursa (job #684143) | Cod sursa (job #1354922) | Cod sursa (job #3259142) | Cod sursa (job #2763009)
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nodd {
int value;
nodd *next;
};
void add_back(nodd *&L, int integer) {
nodd *l = new nodd;
l->value = integer;
l->next = nullptr;
if (L == nullptr)
L = l;
else {
nodd *cop_L = L;
while (cop_L->next != nullptr)
cop_L = cop_L->next;
cop_L->next = l;
}
}
void display(nodd *L) {
while (L != nullptr) {
fout << L->value << " ";
fout << L->value << " ";
L = L->next;
}
}
int n, m, ans;
bitset<100010> viz;
void dfs(int, nodd **);
int main() {
fin >> n >> m;
nodd **L = new nodd *[n + 10];
for (int i = 1; i <= n; i++)
L[i] = new nodd[n + 10];
for (; m != 0; m--) {
int x, y;
fin >> x >> y;
add_back(L[x], y);
add_back(L[y], x);
}
for (int i = 1; i <= n; i++)
if (!viz[i]) {
ans++;
viz[i] = true;
dfs(i, L);
}
fout << ans;
return 0;
}
void dfs(int nod_cur, nodd **L) {
for (nodd *cop_L = L[nod_cur];cop_L!=nullptr; cop_L = cop_L->next)
if (!viz[cop_L->value]) {
viz[cop_L->value] = true;
dfs(cop_L->value, L);
}
}