Pagini recente » Cod sursa (job #1176956) | Cod sursa (job #1226858) | Cod sursa (job #2825545) | Cod sursa (job #1260164) | Cod sursa (job #177220)
Cod sursa(job #177220)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
#define FIN "dfs.in"
#define FOUT "dfs.out"
typedef struct nod
{
int info;
struct nod * next;
} NOD;
NOD * V[NMAX];
int SEL[NMAX];
FILE * fin, * fout;
int N, M;
void push( NOD *& list, int info )
{
NOD * q = new NOD;
q->info = info;
q->next = NULL;
if( !list )
list = q;
else
{
q->next = list;
list = q;
}
}
void DFS( int nod )
{
NOD * tmp;
tmp = V[nod];
while( tmp != NULL )
{
if( !SEL[tmp->info] )
{
SEL[tmp->info] = 1;
DFS( tmp->info);
}
tmp = tmp->next;
}
}
int main()
{
int i, X, Y, nr = 0;
fin = fopen( FIN, "r");
fout = fopen( FOUT, "w" );
fscanf( fin, "%d%d", &N, &M );
for( i = 1; i <= N; i++ )
V[i] = NULL;
while( M )
{
fscanf( fin, "%d%d", &X, &Y );
push( V[X], Y );
push( V[Y], X );
M--;
}
for( i = 1; i <= N; i++ )
if( !SEL[i] )
DFS( i ), nr++;
fprintf( fout, "%d\n", nr );
fclose( fin );
fclose( fout );
}