Pagini recente » Cod sursa (job #3276266) | Cod sursa (job #1612338) | Cod sursa (job #2312494) | Cod sursa (job #412267) | Cod sursa (job #1360572)
// dfs
#include <iostream>
#include <fstream>
#include <vector>
#define NMax 100005
#define pb push_back
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m;
vector<int> V[NMax];
bool viz[NMax];
void read() {
f>>n>>m;
for (int i=1;i<=m;i++) {
int a, b;
f>>a>>b;
V[a].pb(b);
V[b].pb(a);
}
}
void dfs(int node) {
viz[node] = true;
for (unsigned i=0;i<V[node].size();i++) {
int vecin = V[node][i];
if (!viz[vecin])
dfs(vecin);
}
}
void solve() {
int comp = 0;
for (int i=1;i<=n;i++) {
if (!viz[i]) {
comp++;
dfs(i);
}
}
g<<comp<<'\n';
}
int main() {
read();
solve();
f.close(); g.close();
return 0;
}