Cod sursa(job #926164)

Utilizator vandrei95Zamfir Vlad vandrei95 Data 24 martie 2013 23:29:25
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include<fstream>
using namespace std;
struct nod
{
    int vf;
    nod *next;
}*p[100003],*nou;
int viz[100003];
void DF(int vfcrt)
{
    while(p[vfcrt]!=NULL)
        if(viz[p[vfcrt]->vf]==0)
        {
            viz[p[vfcrt]->vf]=1;
            DF(p[vfcrt]->vf);
        }
        else
            p[vfcrt]=p[vfcrt]->next;
}
int main()
{
    fstream f("dfs.in",ios::in), g("dfs.out",ios::out);
    int n,m,i,j,nrC=0,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        nod *nou;
        nou=new nod;
        nou->vf=y;
        nou->next=p[x];
        p[x]=nou;
        nou=new nod;
        nou->vf=x;
        nou->next=p[y];
        p[y]=nou;
    }
    int vfcrt=1,gasit,vecin;

    do
    {
        nrC++;
        viz[vfcrt]=1;
        DF(vfcrt);
        gasit=0;
        for(i=1;i<=n;i++)
            if(viz[i]==0)
            {
                gasit=1;
                vfcrt=i;
            }
    }
    while(gasit);
    g<<nrC;




}