Pagini recente » Cod sursa (job #1851043) | Statistici Andrei Alexandrescu (andrei17052004) | Cod sursa (job #2752489) | Cod sursa (job #1001880)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
struct nod {
bool m;
vector<int> v;
void add(int x) {
v.push_back(x);
};
};
int main() {
ifstream f("dfs.in");
ofstream fout("dfs.out");
int n, m;
int c = 0;
nod p[100001];
f>>n>>m;
for(int i=1;i<=n;i++) p[i].m = false;
for(int i=1;i<=m;i++) {
int x,y;
f>>x>>y;
p[x].add(y);
p[y].add(x);
}
for(int i=1;i<=n;i++) {
if(p[i].m) continue;
c++;
queue<int> q;
q.push(i);
while(!q.empty()) {
for(int k=0;k<(int)p[i].v.size();k++) {
if(!p[p[i].v[k]].m) q.push(p[i].v[k]);
}
p[q.front()].m = true;
q.pop();
}
}
fout<<c<<endl;
return 0;
}