Cod sursa(job #861138)

Utilizator boby301Bogdan Bacila boby301 Data 20 ianuarie 2013 23:59:56
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int a[50][50],n,i,j,x,y,nr=0,m,valid[50];

/*void ScrieMat(int xx[][50],int yy)
{
    int i,j;
    for (i=1;i<=yy;i++)

    {
        for (j=1;j<=yy;j++)
        {
            cout<<xx[i][j]<<" ";
        }
        cout<<endl;
    }

}

void ScrieSir(int xx[],int yy)
{
    int i;
    for (i=1;i<=yy;i++)
    {
        cout<<xx[i]<<' ';

    }
    cout<<endl;
}*/

void CautaVecini(int v)
{
    int i=1,j=1,vecini[50],k;
    vecini[j]=v;
    valid[v]=1;

    while(i<=j)
    {
        for(k=1;k<=n;k++)
        {
            if (a[vecini[i]][k]==1 && valid[k]==0)
            {
                j++;
                vecini[j]=k;
                valid[k]=1;
            }
        }

        i++;
    }
    //ScrieSir(vecini,j);
    nr++;
}

int main()
{

    f>>n>>m;
    //cout<<n<<endl;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        //cout<<x<<" "<<y<<endl;

        a[x][y]=1;
        a[y][x]=1;
    }

    //cout<<endl;
    //ScrieMat (a,n);
    //cout<<endl;

    for (i=1;i<=n;i++)
    {
        if(valid[i]==0)
        {
            CautaVecini(i);
        }
    }

    g<<nr;

    return 0;
}