# Minimum spanning tree 10/100 (risolto)

**URL:** <https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906>\
**Category:** Aiuto\
**Created:** [12 Gennaio 2022, 9:19pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906 "2022-01-12T21:19:33Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [12 Gennaio 2022, 9:19pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/1 "2022-01-12T21:19:33Z")

</div>

Stavo provando a fare un algoritmo per il minimum spanning tree. Ho cercato di seguire il ragionamento del kruskal’s algorithm (lo ho trovato solo implementato con classi e strutture di cui capisco poco), quel che ho fatto è stato inserire i due nodi con la distanza in una priority queue, in modo da ottenere le distanze ordinate, poi finchè la queue non è vuota controlla se i due nodi sono visitati, o raggiungibili, vi allego il programma perchè penso sia più facile comprendere così che a parole:

```auto
#include <bits/stdc++.h>
#define MAXN 10001
using namespace std;
vector<int> adj[MAXN];
priority_queue<pair<int ,pair<int, int> > > pq;
priority_queue<pair<int,int> > pr;
int vis[MAXN];
int c=0;
int vis2[MAXN];
long long Matrix[MAXN][2];
long long N;

void DFS(int s,int end){ //se trova il collegamento che porta il nodo s al nodo end, finisce 
//restituendo 1 a sol, che lo restituisce dove viene chiamato
	if(s==end){
		c=1;
	}
	if(vis2[s]==1 || c==1) return;
	vis2[s]=1;
	for(int u=0;u<adj[s].size();u++){
		DFS(adj[s][u], end);
	}
}

int sol(int s, int end){
	c=0;
	for(int u=0;u<N;u++) vis2[u]=0; 
	DFS(s,end);
	return c;
}

int main(void)
{
	FILE *fr, *fw;
    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
	long long M,i;
	long long a,b,c,r=0;
	assert(2 == fscanf(fr, "%lld%lld", &N, &M)); 
	for(i=0;i<M;i++){
		assert(3 == fscanf(fr, "%lld%lld%lld", &a, &b, &c));
		pq.push(make_pair(-c,make_pair(a,b))); //ordina la queue per distanza
	}
	while(!pq.empty()){
		if((vis[pq.top().second.first]==0 || vis[pq.top().second.second]==0) || (!sol(pq.top().second.first,pq.top().second.second))){ //controlla se entrambi i nodi che hanno tra loro distanza
// minore siano visitati. la funzione invece chiama una DFS perchè
// nel caso siano entrambi già stati visitati bisogna vedere se sono collegati
			vis[pq.top().second.first]=1; //i due nodi sono visitati
			vis[pq.top().second.second]=1;
			adj[pq.top().second.first].push_back(pq.top().second.second); //crea il tree aggiungendo gli archi
			adj[pq.top().second.second].push_back(pq.top().second.first);
			r+=-pq.top().first; //aumenta il risultato della distanza di tale arc
			if(pq.top().second.first<pq.top().second.second)pr.push(make_pair(-pq.top().second.first,-pq.top().second.second)); //normalmente non servirebbe ma il problema 
//sul sito richiede anche i nodi che formano l'albero perciò li salva in un altra queue
// (so che non servirebbe ma dai casi di esempio vedevo che li voleva ordinati e non so se sarebbe errore o meno non metterli così)
			else pr.push(make_pair(-pq.top().second.second,-pq.top().second.first));
		}		
		pq.pop(); //rimuove dalla queue nodi e arco controllati
	}
	fprintf(fw, "%d\n", r);
	while(!pr.empty()){
		fprintf(fw, "%d %d\n", -pr.top().first, -pr.top().second);
		pr.pop();
	}
		
return 0;
}

```

Dall’esercizio mi da qualche risultato sbagliato, se trovate qualche caso in cui non funziona il programma fatemi sapere. (in alcuni casi va anche out di tempo ma onestamente non saprei come velocizzare, al massimo potrei fare un altra if che fa controllare tutto il grafo solo quando entrambi i nodi sono già stati visitati)

---

<div class="post-metadata">

**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\
**Post date:** [13 Gennaio 2022, 8:52am UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/2 "2022-01-13T08:52:40Z")

</div>

Non riesco a debuggare il codice perché non ho il pc ma ti so dire che l’algoritmo di kruskal è molto molto più facile utilizzando le disjoint set union (dsu)  
Da quello che vedo sembra tu sia incappato in un’implementazione un po’ molto forzata e inutilmente complessa  
[[PO2022] Algoritmi e nozioni base sui grafi - YouTube](https://youtu.be/j3JTW445TOw) qua trovi una implementazione pulita delle dsu e da lì è molto facile implementare kruskal (fatte le 3 funzioni make\_set, find e join della dsu sono letteralmente 5 o 6 righe)

---

<div class="post-metadata">

**Author:** ![edomora97](https://forum.olinfo.it/user_avatar/forum.olinfo.it/edomora97/32/712_2.png) [@edomora97](https://forum.olinfo.it/u/edomora97)\
**Post date:** [13 Gennaio 2022, 9:54am UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/3 "2022-01-13T09:54:18Z")

</div>

Wow che bella lezione! 👀

Ci sono anche i capitoli, quindi puoi saltare subito a _Minimum Spanning Tree_ (1:11:40).

---

<div class="post-metadata">

**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\
**Post date:** [13 Gennaio 2022, 1:51pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/4 "2022-01-13T13:51:14Z")

</div>

Slides gentilmente prese in prestito da Giada Franz 👀

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [13 Gennaio 2022, 2:14pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/5 "2022-01-13T14:14:27Z")

</div>

ho visto il video, grazie, spiegato molto bene (per quello che dici (se sei tu a spiegare nel video) al min 1:47:57 si lo sei, vedendo che sei riuscito a farlo capire ad uno studente delle superiori), più tardi proverò ad implementarlo e vi farò sapere se ho problemi

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [14 Gennaio 2022, 5:06pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/6 "2022-01-14T17:06:58Z")

</div>

stavo rivedendo l’implementazione fatta nel video, e non mi è chiaro il funzionamento della funzione _sort(A.begin(), A.end(), comp);_ , come già detto non so come funzionino le strutture perciò volevo capire esattamente cosa prende di A quando esegue questa parte? E la funzione comp che si usa per ordinarlo come va scritta? mi da sempre un errore rimandandomi a questo` template<typename _Iterator1, typename _Iterator2> bool operator()(_Iterator1 __it1, _Iterator2__ it2) const { return * __it1 < *__ it2; } };`

Ho provato sia togliendo la funzione comp , che crearla così

```auto
bool comp (int i,int j) { return (i<j); }

```

Come posso fare?  
Il programma intero è questo:

```auto
#include <bits/stdc++.h>
#define MAXN 10001
using namespace std;
struct arco_t{
	int a,b;
	long long w;
};

vector<arco_t> A;
long long sol;
vector <arco_t> archi_sol;
int P[MAXN], R[MAXN];

void MAKE_SET(int x){
	P[x] = x;
	R[x] = 0;
}
int FIND(int x){
	if (P[x]==x) return x;
	else return P[x] = FIND(P[x]);
}

void UNION(int a, int b){
	a = FIND(a);
	b = FIND(b);
	if(a!=b){
		if(R[a] < R[b]){
			P[a]=b;
		}else{
			P[b]=a;
			if(R[a]== R[b]) R[a]++;
		}
	}
}
int main(){
	int i, N,M;
	cin >> N >> M;
	for(i=0;i<M;i++){
		cin >> A[i].a >> A[i].b >> A[i].w;
	}
	sort(A.begin(), A.end(), comp);
	for(i=0;i<N;i++) MAKE_SET(i);
	for(i=0;i<M;i++){
		if(FIND(A[i].a) != FIND(A[i].b)){
			UNION(A[i].a, A[i].b);
			sol = sol + A[i].w;
			archi_sol.push_back(A[i]);
		}
	}
return 0;
}

```

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [14 Gennaio 2022, 6:35pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/7 "2022-01-14T18:35:26Z")

</div>

Dobbiamo ordinare gli archi crescenti per il loro peso w:  
La funzione comp (compara) lavora col campo w delle due istanze di tipo arco\_t che le vengono passate come parametri ed il valore che restituisce permette alla funzione sort (che la chiama tutte le volte che le serve) di sapere quale dei due parametri ha il w maggiore.  
più o meno dovrebbe essere così

> [@JOVAinter12](#):
>
> `bool comp (const arco_t& i,const arco_t& j) { return (i.w<j.w); }`

non azzecco mai il verso della disequazione ma basta provare se con \< ordina crescente  
col \> ordina decrescente o viceversa.

D’altra parte la sort è pensata per ordinare qualunque tipo di dato ma l’unica cosa che spesso non sa fare è stabilire fra due dati di uno stesso tipo chi sia il maggiore…

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [14 Gennaio 2022, 6:48pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/8 "2022-01-14T18:48:48Z")

</div>

ok ora me lo fa eseguire, grazie, però ora ho un altro problema , cioè quando vado ad eseguire ed incollo i dati (il caso di esempio nel problema sul sito) smette di funzionare(si chiude il terminale), probabilmente ho sbagliato qualcosa qua:

```auto
for(i=0;i<M;i++){
		cin >> A[i].a >> A[i].b >> A[i].w;
	}

```

oppure in qualche passaggio prima

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [14 Gennaio 2022, 6:57pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/9 "2022-01-14T18:57:53Z")

</div>

Sto guardando e da problemi anche sul mio sistema di sviluppo comunque è un vecchio problema e questi leggono i dati dal file “input.txt” e scrivono il risultato sul file “output.txt”  
quindi in testa subito sotto al al main():

> freopen(“input.txt”, “r”, stdin);  
> freopen(“output.txt”, “w”, stdout);

a parte questo qualcosa non mi convince:  
chiami le FIND prima di chiamare La UNION e dentro la UNION richiami le FIND

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [14 Gennaio 2022, 7:04pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/10 "2022-01-14T19:04:59Z")

</div>

si si li avrei aggiunti dopo, non mi trovo molto da file quindi faccio sempre senza e prima di sottoporre aggiungo le varie cose, comunque anche aggiungendoli mi si chiude dando errore.  
Per quanto riguarda le FIND quelle dell’if nel main servono per controllare se i due nodi appartengono allo stesso albero, e in caso non lo siano le unisce tramite UNION. Le due FIND all’interno dell UNION invece servono per vedere se collegare l’albero a cui appartiene il nodo a all’albero del nodo b o viceversa (in pratica prende il nodo più “alto” del proprio albero)

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [14 Gennaio 2022, 7:09pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/11 "2022-01-14T19:09:54Z")

</div>

Sono andato avanti col debug:  
Ti si pianta perchè non hai dimensionato A:  
non puoi mettere i dati dentro A in quel modo (E’ un vettore di dimensione 0):  
O prima fai A.resize(M); // gli archi sono M  
o metti dentro i dati a suon di push\_back.

con A.resize(M) dopo aver letto M legge, ordina e va fino in fondo peccato che non stampi niente.  
Infine mi risulta che dovrebbe essere la Union a chiamare al suo interno le Find per sapere se quell’arco crea un loop o meno per poi regolarsi di conseguenza.

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [14 Gennaio 2022, 7:15pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/12 "2022-01-14T19:15:26Z")

</div>

ok grazie, effettivamente non avevo dato dimensione, aggiungedolo e aggiungendo i cout mi da 100/100. Comunque cosa intendi qua

> [@v.bizzarri](#):
>
> Infine mi risulta che dovrebbe essere la Union a chiamare al suo interno le Find per sapere se quell’arco crea un loop o meno per poi regolarsi di conseguenza.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [14 Gennaio 2022, 7:26pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/13 "2022-01-14T19:26:59Z")

</div>

Ma il metodo in italiano sta per Unione di Insiemi Disgiunti:  
Passo alla Union i vertici che l’arco collega e la Union mediante le due chiamate alla Find viene a sapere se i due vertici fanno parte dello stesso insieme (se i due vertici hanno lo stesso progenitore, la stessa radice) oppure no.  
SE si no aggiunge all’albero quell’arco e in questo caso non conteggia il suo peso.  
Se si lo aggiunge all’albero, ne conteggia il peso, infine unisce i due insiemi e in base al rank (R) dei due insiemi stabilisce quale quale dei due (pro)genitori diventa il progenitore anche di tutti gli elementi dell’altro insieme

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [14 Gennaio 2022, 7:32pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/14 "2022-01-14T19:32:29Z")

</div>

ed è ciò che fa il mio programma in teoria, magari mi sono espresso male prima o ho confuso qualcosa, grazie dell’aiuto 🙂

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [14 Gennaio 2022, 9:30pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/15 "2022-01-14T21:30:42Z")

</div>

Se vuoi ti mando in privato la soluzione con le Find chiamate dentro la Union.  
In generale la union è come la sort è aspecifica ma di volta la si può in parte modificare per renderla ad hoc per il dato problema, oppure se chiami le Find prima di chiamare la union prova a passare alla union direttamente i progenitori così la Union non dovrà richiamare di nuovo le Find.  
Tieni presente per quanto riguarda i tempi di elaborazione la più onerosa è la find (è ricorsiva), va usata il minimo possibile.

---

<div class="post-metadata">

**Author:** ![JOVAinter12](https://forum.olinfo.it/user_avatar/forum.olinfo.it/jovainter12/32/862_2.png) [@JOVAinter12](https://forum.olinfo.it/u/JOVAinter12)\
**Post date:** [14 Gennaio 2022, 9:51pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/16 "2022-01-14T21:51:06Z")

</div>

Come preferisci, a questo punto sono curioso ma dove sono le chat private?

---

<div class="post-metadata">

**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\
**Post date:** [14 Gennaio 2022, 10:26pm UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/17 "2022-01-14T22:26:54Z")

</div>

la find non va in tempo `O(n/ackermann(n))` che e’ quindi `O(1)`? (ovviamente con path compression e merge ottimale)

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [15 Gennaio 2022, 9:16am UTC](https://forum.olinfo.it/t/minimum-spanning-tree-10-100-risolto/6906/18 "2022-01-15T09:16:17Z")

</div>

Sì, con path compression ed union by rank la complessità delle varie operazioni corrisponde all’inversa di ackermann. Da un punto di vista teorico è diverso da O(1) ma in pratica ci è moooolto vicino.