Il mio algoritmo costruisce prima il grafo delle relazioni, poi lo scorro fino in fondo annotandomi nell’array S di output il primo nodo che ha un maggior numero di relazioni non già incluse da un altro nodo. Questo processo viene iterato più volte, fino a che i nodi scelti includono tutte le relazioni. Così si costruisce la soluzione in maniera molto veloce.
Per esempio, guardando il secondo esempio, il grafo delle relazioni sarebbe così:
1 4 3
2 4 9
3 1 8 5
4 1 2
5 8 11 3 6
6 9 10 8 5
7 8 11
8 7 5 3 6
9 10 6 2
10 9 6
11 5 7
dunque nell’array andranno salvati rispettivamente i nodi 5,2, 1, 6, 7 che includono tutte le relazioni.
E nonostante contengano tutte le relazioni, dà comunque output errato, come in tutti i casi tranne il primo esempio.
Non so forse ho compreso la consegna in un’altra maniera, any help? 
Nel secondo caso d’esempio 5, 2, 1, 6, 7 è una tra le soluzioni possibili. Controlla che non ci siano variabili non inizializzate e di aver opportunamente riempito il vettore S da 0 a valore\_restituito - 1
1 Mi Piace
mi pare di aver controllato bene, ma non c’è niente da fare, quell’output per qualche ragione è errato
lascio il codice di seguito…
Mi sono permesso di modificare il grader, in quanto è buggoso sul mio compilatore per qualche ragione…
#include <bits/stdc++.h>
using namespace std;
struct blocco{
int c;
int i;
};
int N;
int M;
int* A;
int* B;
int* S;
int res;
// Declaring functions
int riassumi(int N, int M, int* A, int* B, int* S);
int main() {
ifstream in("input.txt");
ofstream out("output.txt");
// Iterators used in for loops
int i0;
// Reading input
in >> N >>M;
A = (int*)malloc(M * sizeof(int));
B = (int*)malloc(M * sizeof(int));
S = (int*)malloc(10 * sizeof(int));
for (i0 = 0; i0 < M; i0++) {
in >> A[i0] >> B[i0];
}
// Calling functions
res = riassumi(N, M, A, B, S);
// Writing output
cout << res << endl;
for (i0 = 0; i0 < res; i0++) {
cout << S[i0] << " ";
}
in.close();
out.close();
return 0;
}
int riassumi(int N, int M, int A[], int B[], int S[]) {
vector<bool> visitato;
vector<vector<int>>relazioni;
int rimanenti=N,i,j,nodi=0,dim;
struct blocco best,current;
//Popolo il grafo
visitato.assign(N+1,false);
relazioni.assign(N+1,vector<int>());
for(i=0;i<M;i++){
relazioni[A[i]].push_back(B[i]);
relazioni[B[i]].push_back(A[i]);
}
/*cout << "stampa grafo:\n" << N << endl;
for(i=1;i<N+1;i++){
cout << i << "\t";
for(j=0;j<relazioni[i].size();j++)
cout << relazioni[i][j] << " ";
cout << endl;
}*/
//cout << "best indexes: ";
while(rimanenti>0){
best.c=-1;
best.i=-1;
//Trovo riga del grafo con maggior numero di non visitati
for (i = 1; i < N+1; i++){
current.i=i;
if(visitato[i]==false)
current.c=1;
else
current.c=0;
for(j=0,dim=relazioni[i].size();j<dim;j++){
if(visitato[relazioni[i][j]]==false)
current.c++;
}
if(current.c>best.c)
best=current;
}
//cout << best.i << " ";
//if(visitato[best.i]==false){
S[nodi++]=best.i;
visitato[best.i]=true;
//}
for(j=0,dim=relazioni[best.i].size();j<dim;j++)
if(visitato[relazioni[best.i][j]]==false)
visitato[relazioni[best.i][j]]=true;
rimanenti-=best.c;
}
/*
cout << "\narray finale \n" << nodi << endl;
for(i=0;i<nodi;i++)
cout << S[i] << " ";
*/
return nodi;
}
Ops, ricordavo male l’esercizio ed effettivamente 5, 2, 6, 1, 7 non è soluzione.
Il testo cita " il report finale contenga comunque la descrizione di tutte le relazioni", quindi anche gli archi (9, 10), (3, 8) devono essere considerati. Nella tua soluzione, nessun punto di interessa copre quelle due relazioni.
Non confondere le relazioni(archi) con i punti di interesse (nodi).
1 Mi Piace
Ahhh hai ragione…grazie mille. Non so perché ho pensato che nodo=relazione 
