Cod sursa(job #146415)

Utilizator cos_minBondane Cosmin cos_min Data 1 martie 2008 18:01:42
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "dfs.in"
#define out "dfs.out"
#define dim 100001

int N, M;
bool Sel[dim];

typedef struct NOD {
        int vf;
        NOD* next;
} *PNOD;

PNOD L[dim];

void DF(int);
void Add(int,int);

int main()
{
    int X, Y, T=0;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &M);
    for ( ; M; M-- )
        scanf("%d%d", &X, &Y), Add(X,Y);
    
    for ( int i = 1; i <= N; i++ )
        if ( !Sel[i] ) DF(i), T++;
    
    printf("%d\n", T);
}

void Add(int i, int j)
{
     PNOD q = new NOD;
     q->vf = j;
     q->next = L[i];
     L[i] = q;
}

void DF(int nod)
{
     Sel[nod] = 1;
     
     for ( PNOD q = L[nod]; q; q=q->next )
         if ( !Sel[q->vf] ) DF(q->vf);
}