Cod sursa(job #373648)

Utilizator cristikIvan Cristian cristik Data 14 decembrie 2009 17:10:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#define max 100010
struct lista
{
    int nod;
    lista *next;
};
lista *g[max];
char s[max];
int n,m,comp,i,j,stack[max],top;
void dfs(int nod)
{
    int w;
    stack[++top]=nod;
    s[nod]=1;
    while(top)
    {
        w=stack[top--]; //printf("%d ",w);
         for(; g[w]!=NULL; g[w]=g[w]->next)
             if(!s[g[w]->nod])
              {
                s[g[w]->nod]=1;
                stack[++top]=g[w]->nod;
              }


    }
}
void push(int i,int j)
{
    lista *p=new lista;
    p->nod=j;
    p->next=g[i];
    g[i]=p;
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(; m>0; m--)
    {
        scanf("%d%d",&i,&j);
        push(i,j);
        push(j,i);
    }
    for(i=1; i<=n; i++)
     if(!s[i]) { comp++; dfs(i); }
    printf("%d",comp);
    return 0;
}