Cod sursa(job #540167)

Utilizator DanceKrissCristian Oancea DanceKriss Data 23 februarie 2011 19:29:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include<stdio.h>

using namespace std;

const int LG = (1<<17);
int n,m,
    viz[LG];
typedef struct nod
    {
        int inf;
        nod *next;
    } LIST;
LIST *v[LG],*aux;

void add(int x, int y)
{
    aux=new LIST;
    aux->inf=y;
    aux->next=v[x];
    v[x]=aux;

}

void citire()
{
    int i,x,y;
    cin>>n>>m;
    for( i=1; i<=m; i++ )
    {
        cin>>x>>y;
        add( x,y );
        add( y,x );
    }
}

void dfs(int you)
{
    LIST *p;
    p=v[you];
    while(p)
    {
        if(!viz[p->inf])
            {
                viz[p->inf]=1;
                dfs(p->inf);
            }
        p=p->next;
    }
}

void solve()
{
    int x=0,i;
    for( i=1; i<=n; i++ )
        if(!viz[i])
            {
             x++;
             dfs(i);
            }
    cout<<x<<"\n";

}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    citire();
    solve();

    return 0;
}