Cod sursa(job #700234)

Utilizator wamfeverDobos Ionut wamfever Data 1 martie 2012 08:27:04
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
int n, m, t;
int T[100], D[100], F[100], U[100];

struct lista{
                int nod;
                    lista *urm;
            } *G[100];

void adauga(int i, int j)
{
    lista *p;
    p = new lista;
    p->nod = j;
    p->urm = G[i];
    G[i] = p;
}

void citire()
{
    f >> n >> m;
    int i, j;
    while(m--)
    {
        f >> i >> j;
        adauga(i, j);
        adauga(j, i);
    }
}

void DF(int nod)
{
    lista *p;
    U[nod] = 1;
    //g << nod << " ";

    for(p = G[nod]; p!=NULL; p = p->urm)
        if(!U[p->nod])
        {
           T[p->nod] = nod;
           DF(p->nod);
        }
}

int main()
{
    citire();
    //g << "Componente conexe\n";
    int nr=0;
    for(int i=1; i<=n; i++)
    {
        if(!U[i])
        {
            nr++;
            //g << nr << ": ";
            DF(i);
            //g << "\n";
        }
    }

    g << nr << "\n";

    return 0;
}