Cod sursa(job #913672)

Utilizator rotarraresRotar Rares rotarrares Data 13 martie 2013 18:03:54
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <stdlib.h>
using namespace std;

typedef struct s_nod
{
    int info;
    s_nod *next;
} nod;

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

int n,i,m,a,b,c=0;

nod *graf[100000];
bool exista[100000];

void verificare(int k)
{
    nod *index2;
    if (graf[k])
    {
        index2 = graf[k];
        if (!exista[k])
        {

            exista[k]=true;
            while(index2)
            {
                verificare(index2->info);
                index2=index2->next;
            }
        }
    }
    else
        exista[k]=true;
}

void dfs()
{
    for (i=0; i<n; i++)
    {
        if (!exista[i])
        {
            c++;
            verificare(i);
        }
    }
}

int main()
{
    nod *index;
    f >> n >> m;
    for (i=0; i<m; i++)
    {
        f >> a >> b;
        index = (nod*) malloc (sizeof(nod));
        if(!index) return 0;
        index->info = a;
        index->next= graf[b];
        graf[b]=index;

        index = (nod*) malloc (sizeof(nod));
        if(!index) return 0;
        index->info= b;
        index->next = graf[a];
        graf[a]=index;

    }
    dfs();
    g << c;
    g.close();
    return 0;
}