Cod sursa(job #1554847)

Utilizator antanaAntonia Boca antana Data 21 decembrie 2015 20:26:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#define MAX 100000
using namespace std;
struct nodul{
    int val;
    nodul *next;
};
nodul *v[MAX+1];
void adauga(int nod, int vecin)
{
    nodul *aux;
    aux=new nodul;
    aux->val=vecin;
    aux->next=v[nod];
    v[nod]=aux;
}
int viz[MAX+1];
void dfs(int nod)
{
    nodul *aux;
    viz[nod]=1;
    aux=v[nod];
    while(aux!=NULL)
    {
        if(viz[aux->val]==0)
            dfs(aux->val);
        aux=aux->next;
    }
}
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int x, y,n, m, i;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &x, &y);
        adauga(x, y);
        adauga(y, x);
    }
    int cc=0;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0){
            cc++;
            dfs(i);
        }
    }
    printf("%d", cc);
    return 0;
}