Pagini recente » Cod sursa (job #854998) | Cod sursa (job #1719035) | Cod sursa (job #1104994) | Cod sursa (job #1089130) | Cod sursa (job #2225230)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int key;
struct node* next;
}node;
node* adj[100001];
int descoperit[100001];
void enqueue(node** first, int key) {
node* p = (node *)malloc(sizeof(node));
if (p == NULL) {
perror("malloc failed");
}
p->key = key;
p->next = NULL;
if (*first == NULL) {
*first = p;
}
else{
node* q = *first;
while (q->next != NULL) {
q = q->next;
}
q->next = p;
}
}
void DFS(int s) {
descoperit[s] = 1;
node* p = adj[s];
while (p) {
if (descoperit[p->key] == 0) {
DFS(p->key);
}
p = p->next;
}
}
int main() {
FILE* ip;
FILE* op;
ip = fopen("dfs.in", "r");
if (ip == NULL) {
perror("Error opening input file");
return 1;
}
op = fopen("dfs.out", "w");
if (op == NULL) {
perror("Error opening output file");
return 1;
}
int n, m;
fscanf(ip, "%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int x, y;
fscanf(ip, "%d%d", &x, &y);
enqueue(&adj[x], y);
enqueue(&adj[y], x);
}
int componente_conexe = 0;
for (int i = 1; i <= n; i++) {
if (descoperit[i] == 0) {
DFS(i);
componente_conexe++;
}
}
fprintf(op, "%d", componente_conexe);
fclose(ip);
fclose(op);
return 0;
}