Pagini recente » Cod sursa (job #882053) | Cod sursa (job #613894) | Cod sursa (job #904659) | Cod sursa (job #1448123) | Cod sursa (job #981191)
Cod sursa(job #981191)
#include<stdio.h>
#define NMAX 100001
struct Node{
int value;
struct Node *next;
};
struct Node *L[NMAX];
int N, M, visited[NMAX], conexe = 0;
int min(int a, int b){
if(a < b)
return a;
return b;
}
void read(FILE *pf){
int i, u, v;
struct Node *p, *q;
fscanf(pf, "%d %d", &N, &M);
if(M >= 200000)
M = min(200000, N * (N + 1) / 2);
for(i = 1; i <= M; i++){
fscanf(pf, "%d %d", &u, &v);
p = new Node;
p->value = v;
p->next = L[u];
L[u] = p;
q = new Node;
q->value = u;
q->next = L[v];
L[v] = q;
}
}
void DFS(int u){
int v;
struct Node *p;
visited[u] = 1;
p = L[u];
while(p != NULL){
v = p->value;
if(visited[v] == 0)
DFS(v);
p = p->next;
}
}
int main(){
int i;
FILE *pf, *pg;
pf = fopen("dfs.in", "r");
pg = fopen("dfs.out", "w");
read(pf);
for(i = 1; i <= N; i++)
if(visited[i] == 0){
DFS(i);
conexe++;
}
fprintf(pg, "%d", conexe);
fclose(pf);
fclose(pg);
return 0;
}