Cod sursa(job #1315780)

Utilizator Toast97Calin Farcas Toast97 Data 13 ianuarie 2015 08:33:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;

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

struct nod
{
    int info;
    nod *adr;
};

nod *v[100005];

void adaugare (int nr, int info)
{
    nod *c;
    c = new nod;

    c -> info = info;
    c -> adr = v[nr];

    v[nr] = c;
}

int n, m, x, y;
int viz[100005];

void citire ()
{
    f >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        f >> x >> y;
        adaugare (x, y);
        adaugare (y, x);
    }
}

void dfs (int nr)
{
    viz[nr] = 1;

    nod *p;
    p = v[nr];

    while (p)
    {
        if (!viz[p -> info])
            dfs (p -> info);

        p = p -> adr;
    }
}

int main()
{
    int nc = 0;

    citire ();

    for (int i = 1; i <= n; i ++)
    {
        if (!viz[i])
        {
            ++ nc;
            dfs (i);
        }
    }

    g << nc;

    f.close ();
    g.close ();
    return 0;
}