Cod sursa(job #1598695)

Utilizator gorni97aaa aaa gorni97 Data 13 februarie 2016 11:11:56
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#define maxn 1005
using namespace std;
int a[maxn][maxn],viz[maxn],n,x[maxn];
fstream g("dfs.out",ios::out);


void conex(int S)
{int k,i,nr=0;
for(i=1;i<=n;i++)
    viz[i]=-1;
    x[k]=S;

k=1;
while(k>0)
{S=x[k];
k--;
viz[S]=nr;
for(i=1;i<=n;i++)
    if((a[i][S]==1)&&(viz[i]<0))
{k++;
x[k]=i;
viz[i]=0;}

if(k==0)
    for(i=1;((i<=n)&&(k==0));i++)
     if(viz[i]<0)
{k++;
x[k]=i;
nr++;}

}

    g<<nr;


}

int main()

{int i,m,x,y;
fstream f("dfs.in",ios::in);

f>>n>>m;
for(x=1;x<=n;x++)
    for(y=1;y<=n;y++)
    a[x][y]=0;


for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;
a[y][x]=1;}



    conex(1);
f.close();
g.close();

}