Pagini recente » Cod sursa (job #2231284) | Cod sursa (job #652775) | Cod sursa (job #1078981) | Cod sursa (job #2100269) | Cod sursa (job #2005519)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
const int MAX = 100005;
bitset< MAX > used;
void dfs(int n, vector< vector< int > > &v) {
vector< int > st(MAX, 0);
int top = 0;
st[++ top] = n;
used[st[top]] = true;
while(top) {
for(auto x : v[st[top]]) {
if(used[x])
continue;
used[x] = true;
st[++top] = x;
break;
}
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';
}