Pagini recente » Cod sursa (job #1812149) | Cod sursa (job #146507) | Cod sursa (job #2980744) | Cod sursa (job #1040440) | Cod sursa (job #1359386)
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
bool v[1000010];
vector<vector<int> > nodes;
stack<int> st;
int n, m;
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 0 ; i <= n ; ++i) {
vector<int> x;
nodes.push_back(x);
}
for(int i = 0 ; i < m ; ++i) {
int x, y;
scanf("%d%d", &x, &y);
nodes[x].push_back(y);
nodes[y].push_back(x);
}
int count = 0;
for(int i = 1 ; i <= n ; ++i) {
if(!v[i]) {
++count;
st.push(i);
while(!st.empty()) {
int x = st.top();
st.pop();
for(int i : nodes[x]) {
if(!v[i]) {
st.push(i);
v[i] = 1;
}
}
}
}
}
printf("%d", count);
return 0;
}