Pagini recente » Cod sursa (job #301459) | Cod sursa (job #839762) | Cod sursa (job #1056122) | Cod sursa (job #1555241) | Cod sursa (job #763907)
Cod sursa(job #763907)
#include <stdio.h>
#include <stdlib.h>
struct graph
{
int edge;
struct graph *next;
} *G[100001];
int n, nrComponents;
char used[100001];
void df(int vertex)
{
struct graph *p;
used[vertex] = 1;
for(p = G[vertex]; p ; p = p->next)
if( used[p->edge] == 0)
df(p->edge);
}
int main()
{
FILE *in = fopen("dfs.in", "r");
FILE *out = fopen("dfs.out", "w");
struct graph *p;
int m, a, b;
for(fscanf(in, "%d %d", &n, &m); m; m--)
{
fscanf(in, "%d %d", &a, &b);
p = malloc(sizeof(struct graph));
p->edge = b;
p->next = G[a];
G[a] = p;
p = malloc(sizeof(struct graph));
p->edge = a;
p->next = G[b];
G[b] = p;
}
for(; n; n--)
if(used[n] == 0)
nrComponents++,
df(n);
fprintf(out, "%d\n", nrComponents);
fclose(in), fclose(out);
return 0;
}