Pagini recente » Cod sursa (job #1953882) | Cod sursa (job #1275928) | Cod sursa (job #359626) | Cod sursa (job #291663) | Cod sursa (job #1560981)
#include <vector>
#include <cstdio>
using namespace std;
const int MAX_N = 100002;
template <class T>
class Pointer {
public:
Pointer <T> *next;
Pointer <T> *prev;
T value;
Pointer() {
next = NULL;
prev = NULL;
}
};
template <class T>
class Stack {
Pointer <T> *lo = new Pointer <T>;
Pointer <T> *hi = new Pointer <T>;
T value;
public:
Stack() {
lo->next = hi;
hi->prev = lo;
}
void pushElement(T x) {
Pointer <T> *p = new Pointer <T>;
p->value = x;
p->prev = hi;
hi->next = p;
hi = p;
}
void popElement() {
hi = hi->prev;
delete hi->next;
}
T getTop() {
return hi->value;
}
bool isEmpty() {
return lo == hi;
}
};
int n, m, ans;
vector <int> v[MAX_N];
bool vis[MAX_N];
Stack <int> st;
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i = 1; i <= n; ++i) {
if(vis[i] == true) {
continue;
}
ans++;
vis[i] = true;
st.pushElement(i);
while(st.isEmpty() == false) {
int x = st.getTop();
for(int j = v[x].size() - 1; j >= 0; --j) {
int y = v[x][j];
v[x].pop_back();
if(vis[y] == false) {
st.pushElement(y);
vis[y] = true;
break;
}
}
st.popElement();
}
}
printf("%d\n", ans);
return 0;
}