Cod sursa(job #632721)

Utilizator gherghe94Andrei Gherghelau gherghe94 Data 12 noiembrie 2011 10:22:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>

using namespace std;
struct nod
{
    int inf;
    nod *urm;
}*l[100002];
int n,m;
int nr=0;
int viz[100001];
void add_first(int x,nod *&p)
{
    nod *q=new nod;
    q->inf=x;
    q->urm=p;
    p=q;
}
void citire()
{
    freopen("dfs.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        add_first(y,l[x]);
        add_first(x,l[y]);
    }
}
void dfs(int k)
{
    int st=1,fn=1;
    viz[k]=1;
    for(nod *i=l[k];i;i=i->urm)
    {
        if(!viz[i->inf])
        {
            viz[i->inf]=1;
            dfs(i->inf);
        }
    }

}
int main()
{
    freopen("dfs.out","w",stdout);
    citire();
    for(int i=1;i<=n;++i)
    {
        if(viz[i]==0)
        {
            dfs(i);
            nr++;
        }
    }
    printf("%d\n",nr);
    return 0;
}