Pagini recente » Cod sursa (job #2563677) | Cod sursa (job #165152) | Cod sursa (job #1917333) | Cod sursa (job #1137997) | Cod sursa (job #2005522)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
const int MAX = 100005;
bitset< MAX > used;
vector< int > st(MAX, 0);
void dfs(int n, vector< vector< int > > &v) {
int top = 0;
st[++ top] = n;
used[st[top]] = true;
while(top) {
bool ok = false;
for(auto x : v[st[top]]) {
if(used[x])
continue;
ok = true;
used[x] = true;
st[++top] = x;
break;
}
if(!ok)
top --;
}
}
int main() {
int n, m;
cin >> n >> m;
vector< vector< int > > v(n + 1);
for(int i = 1; i <= m; i ++) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
int sol = 0;
for(int i = 1; i <= n; i ++) {
if(used[i])
continue;
sol ++;
dfs(i, v);
}
cout << sol << '\n';
}