Greedy Graf -oarecare probleme la finalizare(putin ajutor)

Acest forum este dedicat intrebarilor de programare care nu-si au locul in unul din celelalte forumuri

Greedy Graf -oarecare probleme la finalizare(putin ajutor)

Mesajde mihaib » 21 Mar 2015, 01:21

Salutare tuturor!
Problema suna cam asa: Se da un graf orientat si sa se afiseze cea mai mare submultime de noduri cu proprietatea ca intre orice doua noduri nu exista latura (nu sunt adiacente nodurile).

#include <iostream>
#include<fstream>
using namespace std;
int a[10][10]; //initializarea matricei de adiacenta cu 0
int main ()
{
int n,i,x,u,j,v[10],initial,y[10],aux,max,poz;
ifstream f("graf.in");
f>>n;
//for(i=1;i<=n;i++) //initializare matrice de adiacenta
//for(j=1;j<=n;j++)
//a[i][j]=0;

while(f>>x>>u) //citirea arcelor si remodelarea matricei
{

a[x][u]=1; a[u][x]=1;

}
for(i=1;i<=n;i++) //citirea arcelor si remodelarea matricei
{ for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}


for(i=1;i<=n;i++)
{ y[i]=0;
for(j=1;j<=n;j++)

if (a[i][j]==0)

y[i]+=1;

}

max=1;poz=1;
for(i=1;i<=n;i++) //aflam nodul cel mai descoperit: nodul care nu este adiacent cu cele mai multe noduri
if(y[i]>max)
{
max=y[i]; //mem.maximul
poz=i; //memoreaza nodul-pozitia
}
k=1; v[k]=poz; //construim vectorul(submultimea) de noduri care indeplinesc conditia


cout<<"Nodul cel mai descoperit este: "<<poz<<endl;
for(i=1;i<=n;i++)
cout<<"Nodul "<<i<<"are : "<<n-y[i]<<" muchii"<<endl;
initial=poz;
do
{i=1;k++;
while(a[poz][i]==0)
i++;
poz=i+1;
v[k]=poz;

}while(poz!=initial);
for(i=1;i<=k;i++)
cout<<v[i]<<" ";
return 0;
}
mihaib
Junior
Junior
 
Mesaje: 2
Membru din: 18 Mar 2015, 21:29
Judet: Olt

Înapoi la Programare generala

Cine este conectat

Utilizatorii ce navighează pe acest forum: Niciun utilizator înregistrat şi 1 vizitator

cron