Cod sursa(job #373349)

Utilizator cristikIvan Cristian cristik Data 13 decembrie 2009 16:29:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 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(lista *p=g[w]; p!=NULL; p=p->next)
         if(!s[p->nod])
         {
             s[p->nod]=1;
             stack[++top]=p->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;
}