Pagini recente » Cod sursa (job #3196673) | Cod sursa (job #894402) | Cod sursa (job #1272437) | Cod sursa (job #2249215) | Cod sursa (job #2041169)
// DFS.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define maxn 100005
typedef struct list {
int node;
struct list * next;
} graph;
void add_edge(graph ** head, int val) {
if ((*head) == NULL) {
(*head) = (graph*)malloc(sizeof(graph));
(*head)->node = val;
(*head)->next = NULL;
} else {
graph * new_node = (graph*)malloc(sizeof(graph));
new_node->node = val;
new_node->next = (*head);
*(head) = new_node;
}
}
void Dfs(graph *G[maxn], int node, int Vis[maxn]) {
graph *it;
Vis[node] = 1;
for (it = G[node]; it != NULL; it = it->next) {
if (Vis[it->node] == 0) {
Dfs(G, it->node, Vis);
}
}
}
void print_list(graph *head, FILE *fout) {
graph *it;
for (it = head; it != NULL; it = it->next) {
fprintf(fout, "%d ", it->node);
}
fprintf(fout, "\n");
}
int main() {
FILE *fin = fopen("dfs.in", "r");
FILE *fout = fopen("dfs.out", "w");
graph * G[maxn];
int i, x, y, n, m, cnt = 0, Vis[maxn];
fscanf(fin, "%d %d", &n, &m);
for (i = 1; i <= n; i++) {
G[i] = NULL;
}
for (i = 0; i < m; i++) {
fscanf(fin, "%d %d", &x, &y);
add_edge(&G[x], y);
add_edge(&G[y], x);
}
memset(Vis, 0, sizeof(Vis));
for (i = 1; i <= n; i++) {
if (Vis[i] == 0) {
Dfs(G, i, Vis);
cnt++;
}
}
fprintf(fout, "%d \n", cnt);
fclose(fin);
fclose(fout);
return 0;
}