Pagini recente » Cod sursa (job #1902266) | Cod sursa (job #2952100) | Cod sursa (job #1406524) | Cod sursa (job #2230561) | Cod sursa (job #2799227)
#include <stdio.h>
#include <ctype.h>
// Program de Mircea Rebengiuc
// inceput pe 2021.11.12
#define MAXN 100000
#define MAXM 100000
#define NIL -1
int viz[MAXN];
int list[MAXN];
int adj[MAXM];
int next[MAXM];
void dfs( int root ){
int i = list[root];
viz[root] = 1;
while( i != NIL ){
if( !viz[adj[i]] )
dfs(adj[i]);
i = next[i];
}
}
FILE *fin, *fout;
static inline int fgetint(){
int n = 0, ch;
while( !isdigit(ch = fgetc(fin)) );
do
n = n * 10 + ch - '0';
while( isdigit(ch = fgetc(fin)) );
return n;
}
int main(){
fin = fopen("dfs.in", "r");
fout = fopen("dfs.out", "w");
int n, m, i, a, b, ans;
n = fgetint();
for( i = 0 ; i < n ; i++ )
list[i] = NIL;
i = 0;
for( m = fgetint() ; m-- ; ){
a = fgetint() - 1;
b = fgetint() - 1;
adj[i] = b;
next[i] = list[a];
list[a] = i++;
adj[i] = a;
next[i] = list[b];
list[b] = i++;
}
ans = 0;
for( i = 0 ; i < n ; i++ )
if( !viz[i] ){
ans++;
dfs(i);
}
fprintf(fout, "%d\n", ans);
fclose(fin);
fclose(fout);
return 0;
}