Pagini recente » Cod sursa (job #41643) | Cod sursa (job #804724)
Cod sursa(job #804724)
#include <cstdio>
#define MAXN 100001
#define MAXM 200001
using namespace std;
struct node {int inf; node* next;};
int n, m, c;
node* a[MAXN];
int viz[MAXN];
void init () {
for (int i=1; i<=n; ++i)
a[i] = NULL;
}
void push (int x, int y) {
node* p;
p = new node;
p->inf = y;
p->next = a[x];
a[x] = p;
}
void read () {
init ();
freopen ("dfs.in", "r", stdin);
scanf ("%d%d", &n, &m);
int i, x, y;
for (i=1; i<=m; ++i) {
scanf ("%d%d", &x, &y);
push (x, y);
push (y, x);
}
fclose (stdin);
}
void DFS (int i) {
node* p;
viz[i] = 1;
for (p=a[i]; p!=NULL; p=p->next)
if (!viz[p->inf])
DFS (p->inf);
}
void solve () {
int i;
for (i=1; i<=n; ++i)
if (viz[i] == 0) {
++c;
DFS (i);
}
freopen ("dfs.out", "w", stdout);
printf ("%d\n", c);
fclose (stdout);
}
int main () {
read ();
solve ();
return 0;
}