Cod sursa(job #911869)

Utilizator dantheroDan Terhesiu danthero Data 11 martie 2013 22:01:58
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define MAX 100001
typedef struct s_nod
{
    int info;
    struct s_nod *next;
} nod;
int n,m,cc=0;
nod *Graf[MAX];
int Used[MAX];

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");


void parcurgere(int i)
{
    nod *index;

    if (Graf[i])
    {

        if (!Used[i])
        {
            Used[i]=1;
            index=Graf[i];
            while (index)
            {
                parcurgere(index->info);
                index=index->next;
            }
        }
    }
    else
    {
        Used[i]=1;
    }

}

void dfs()
{
    int i;
    for (i=0; i<n; i++)
    {
        if (!Used[i])
        {
            cc++;
            parcurgere(i);
        }
    }
}

int main()
{

    nod *NNou;
    int A,B,i;
    f >> n >> m;
    for (i=0; i<m; i++)
    {
        f >> A >> B;
        NNou = (nod*) malloc (sizeof(nod));
        if (!NNou)
        {
            return 1;
        }
        NNou->info=B;
        NNou->next=Graf[A];
        Graf[A]=NNou;

        NNou = (nod*) malloc (sizeof(nod));
        if (!NNou)
        {
            return 1;
        }
        NNou->info=A;
        NNou->next=Graf[B];
        Graf[B]=NNou;
    }
    dfs();
    g << cc;
    f.close();
    g.close();
    return 0;
}