Pagini recente » Cod sursa (job #1106982) | Cod sursa (job #2202132)
#include <fstream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
const int N = 100001, M = 200002;
int vf[2 * M], ant[2 * M], lst[N], nl(0);
bool viz[N];
void adauga(int a, int b) {
vf[++nl] = b;
ant[nl] = lst[a];
lst[a] = nl;
}
void dfs(int nod) {
viz[nod] = true;
int nodc = lst[nod];
while(nodc != 0) {
if (!viz[vf[nodc]]) {
dfs(vf[nodc]);
}
nodc = ant[nodc];
}
}
int main() {
int n, m, x, y;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> x >> y;
adauga(x, y);
adauga(y, x);
}
int comp(0);
for (int i = 1; i <= n; ++i) {
// int nodc = lst[i];
// while(nodc != 0) {
// cout << vf[nodc] << " ";
// if (!viz[vf[nodc]]) {
// dfs(vf[nodc]);
// }
// nodc = ant[nodc];
// }
// cout << "\n";
if (!viz[i]) {
++comp;
dfs(i);
}
}
cout << comp;
return 0;
}