Pagini recente » Cod sursa (job #2076872) | Cod sursa (job #572606) | Cod sursa (job #3042328) | Clasament dot-com2011 | Cod sursa (job #629068)
Cod sursa(job #629068)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define Nmax 100010
int n, m;
int viz[Nmax];
vector <int> V[Nmax];
stack < pair <int, int> >S;
void DFS (int x) {
int nod, i;
viz[x] = 1;
for (S.push ( make_pair (x, 0) ); !S.empty ();) {
nod = S.top ().first;
i = S.top ().second;
while (i < (int)V[nod].size () && viz[V[nod][i]]) i++;
if (i < (int)V[nod].size ()) {
S.top ().second++;
viz[ V[nod][i] ] = 1;
S.push ( make_pair ( V[nod][i], 0 ) );
}
else S.pop ();
}
}
int main () {
freopen ("dfs.in", "r", stdin);
freopen ("dfs.out", "w", stdout);
int x, y;
scanf ("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
V[x].push_back (y);
V[y].push_back (x);
}
int sol = 0;
for (int i = 1; i <= n; i++)
if (viz[i] == 0) sol++, DFS (i);
printf ("%d", sol);
}