Cod sursa(job #582881)

Utilizator stef93Stefan Gilca stef93 Data 16 aprilie 2011 14:31:53
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
using namespace std;

struct Gr{int nod;Gr *next;};
typedef Gr *Lista;
Lista G[10003];
bool u[10003];
int n,m;

void add(int x,int y)
{
    Lista intermed;
    intermed=new Gr;
    intermed->nod=y;
    intermed->next=G[x];
    G[x]=intermed;
}

void dfs(int nod)
{
    u[nod]=1;
    for(Lista it=G[nod];it;it=it->next)
    if(!u[it->nod])
    dfs(it->nod);
}

int main()
{
    int x,y,i,k=0;
    freopen("dfs.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(;m;--m)
    {
        scanf("%d %d",&x,&y);
        add(x,y);
        add(y,x);
    }
    fclose(stdin);
    for(i=1;i<=n;i++)
    if(!u[i])
    {
        dfs(i);
        ++k;
    }
    freopen("dfs.out","w",stdout);
    printf("%d\n",k);
    fclose(stdout);
    return 0;
}