Cod sursa(job #209860)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 25 septembrie 2008 09:22:45
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#define MAX 1000001

using namespace std;

ifstream fin ("Breadth_First_Search.in");
ofstream fout("Breadth First Search.out");

int n,m,viz[MAX]

struct nod
{
    int inf;
    nod *urm;
};
typedef struct nod nod;
nod * sir[100001];

void baga(int x,int y)
{
    nod * q=new nod;
    q->inf=x;
    q->urm=sir[y];
    sir[y]=q;
}

void citire()
{
    fin>>n>>m;
    int a,b;
    for (int i=0;i<=n;i++)
        sir[i]=NULL;
    for (int i=0;i<=m;i++)
    {
        fin>>a>>b;
        baga(a,b);
        baga(b,a);
    }
}


void fsd(int lol)
{
    viz[lol]=1;
    while (sir[lol])
    {
        if (!viz[sir[lol]->inf])
        {
            viz[sir[lol]->inf]=1;
            fsd(sir[lol]->inf);
        }
        sir[lol]->urm;
    }
}


int main ()
{
    citire();
    int nr=0;
    for (int i=1;i<=n;i++)
        if (!viz[i])
        {
                fsd(i);
            nr++;
        }
    return 0;
}