Pagini recente » Autentificare | Atasamentele paginii Profil szzsvbvyyaz | Cod sursa (job #3324472) | Atasamentele paginii Profil sara_andreea_matei | Cod sursa (job #1607108)
#include <stdio.h>
#define IN "dfs.in"
#define OUT "dfs.out"
#define MAXN 100001
typedef struct _GRAPH{
int node;
struct _GRAPH *next;
} GRAPH;
int n, m, counter = 0, seen [MAXN];
GRAPH *graph [MAXN];
inline void add (int location, int node0){
GRAPH *p = (GRAPH*) malloc (sizeof (GRAPH));
p -> node = node0;
p -> next = graph [location];
graph [location] = p;
}
void read (void){
int i, edge1, edge2;
scanf ("%d%d", &n, &m);
for (i = 1; i <= m; ++i){
scanf ("%d%d", &edge1, &edge2);
add (edge1, edge2);
add (edge2, edge1);
}
}
void dfs (int node0){
GRAPH *node = graph [node0];
seen [node0] = 1;
while (node){
if (! seen [node -> node])
dfs (node -> node);
node = node -> next;
}
}
int main (void){
freopen (IN, "r", stdin);
freopen (OUT, "w", stdout);
read();
int i;
for (i = 1; i <= n; ++ i)
if (!seen [i]){
++ counter;
dfs (i);
}
printf ("%d", counter);
fclose (stdin);
fclose (stdout);
return 0;
}