Cod sursa(job #899731)

Utilizator alexsuciuAlex Suciu alexsuciu Data 28 februarie 2013 15:59:30
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<iostream>
using namespace std;
int n,q[10000],viz[5000],i,j,t[2][5000],v[5000],p,m;

void  citire(int &n,int &m)
{
    int i,j,k=0;
    ifstream f("dfs.in");
    f>>n>>m;
    while(f>>i>>j)
    {
        k++;
        t[0][k]=j;
        t[1][k]=v[i];
        v[i]=k;
        k++;
        t[0][k]=i;
        t[1][k]=v[j];
        v[j]=k;
    }
}
void bf(int x)
{int i=1,j=1;
    q[i]=x;
    viz[x]=1;
    while(i<=j)
    {p=v[q[i]];
    while (p)
    {
        if(viz[t[0][p]]==0)
        {
            j++;
            q[j]=t[0][p];
            viz[t[0][p]]=1;
        }
            p=t[1][p];
    }
    i++;
    }
}



int main()
{int nr=0;
ofstream g("dfs.out");
    citire(n,m);
 for(i=1;i<=n;i++)
 if(viz[i]==0) {nr++;
bf(i);

}
g<<nr;}