Completing a Tree

PhylogenyGraph Algorithms

Descrizione

Un albero è un grafo connesso senza cicli. Data una lista di adiacenza corrispondente a un grafo su n nodi senza cicli (ma non necessariamente connesso), il problema chiede il numero minimo di archi da aggiungere per trasformare il grafo in un albero (cioè per renderlo completamente connesso senza introdurre cicli).

Given

Un intero positivo n (n ≤ 1000) e una lista di adiacenza corrispondente a un grafo su n nodi che non contiene cicli.

Return

Il numero minimo di archi che possono essere aggiunti al grafo per produrre un albero.

Sample Dataset

Sample Output

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

Output · run_log.txt

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

#http://rosalind.info/problems/tree/

#10
#1 2
#2 8
#4 10
#5 9
#6 10
#7 9

def lettura(filename):
    dati = []
    with open(filename) as f:
         n = int(f.readline().replace("\n", ""))
         for riga in f:
             #dati.append(list(map(int, riga.replace("\n", "").split(" "))))
             dati.append(riga.replace("\n", "").split(" "))
    return n, dati        

#http://www.bogotobogo.com/python/python_graph_data_structures.php
        
class Vertex:
    def __init__(self, node):
        self.id = node
        self.adjacent = {}

    def __str__(self):
        return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight

    def get_connections(self):
        return self.adjacent.keys()  

    def get_id(self):
        return self.id

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

class Graph:
    def __init__(self):
        self.vert_dict = {}
        self.num_vertices = 0

    def __iter__(self):
        return iter(self.vert_dict.values())

    def add_vertex(self, node):
        self.num_vertices = self.num_vertices + 1
        new_vertex = Vertex(node)
        self.vert_dict[node] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.vert_dict:
            return self.vert_dict[n]
        else:
            return None

    def add_edge(self, frm, to, cost = 0):
        if frm not in self.vert_dict:
            self.add_vertex(frm)
        if to not in self.vert_dict:
            self.add_vertex(to)

        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

    def get_vertices(self):
        return self.vert_dict.keys()
         
def main():
    n, dati = lettura("dataset.txt")
    #print(dati)
    #[['1', '2'], ['2', '8'], ['4', '10'], ['5', '9'], ['6', '10'], ['7', '9']]
    
    g = Graph()

    for i in range(n):
        g.add_vertex(str(i+1))

    for pair in dati:
        g.add_edge(pair[0], pair[1])  

    #for v in g:
        #for w in v.get_connections():
            #vid = v.get_id()
            #wid = w.get_id()
            #print(vid, wid)

        #1 2
        #2 1
        #2 8
        #4 10
        #5 9
        #6 10
        #7 9
        #8 2
        #9 5
        #9 7
        #10 4
        #10 6

    sets = []
    for v in g:
        setv = {v.get_id()} | {x.id for x in v.adjacent}
        found = False 
        for i in range(len(sets)):
            if len(setv & sets[i]) > 0:
               sets[i] = sets[i] | setv
               found = True
               break
        if not found:     
           sets.append(setv)             
    
    #print(sets)
    print("", len(sets)-1)
    # 3
            
if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Completing a Tree (Rosalind ID: TREE) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica per
// contare le componenti connesse, riscritta in modo idiomatico per JS.
//
// ATTENZIONE - bug riprodotto intenzionalmente: per ogni vertice v,
// problem.py unisce l'insieme {v} ∪ vicini(v) al PRIMO insieme già
// esistente con cui interseca, senza controllare se dovrebbe unirsi
// anche ad altri insiemi già creati in precedenza. Su certe topologie
// (es. un vertice "ponte" che collega due gruppi già registrati come
// insiemi separati) questo può produrre più componenti di quelle
// realmente connesse, sovrastimando gli archi mancanti - un vero e
// proprio bug rispetto a un union-find corretto. Qui è riprodotto
// fedelmente - non corretto - perché il confronto "Corrisponde
// all'output registrato" si basa sull'output REALE già salvato in
// run_log.txt (che contiene lo stesso comportamento).
//
// Nota sul formato: come in inod.mjs, problem.py fa
// print("", len(sets)-1), che con il separatore di default di print
// produce uno SPAZIO INIZIALE prima del numero - riprodotto identico.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
function lettura(datasetText) {
  const righe = datasetText.split("\n").map((r) => r.replace(/\r$/, ""));
  const n = Number(righe[0]);
  const dati = righe
    .slice(1)
    .filter((r) => r !== "")
    .map((r) => r.split(" "));
  return { n, dati };
}

export default function solve(datasetText) {
  const { n, dati } = lettura(datasetText);

  if (!Number.isInteger(n) || n < 1) {
    throw new Error("Input non valido: attesa una prima riga con il numero di vertici");
  }

  // Adiacenza simmetrica, come Graph.add_edge in problem.py.
  const adiacenza = new Map();
  for (let i = 1; i <= n; i++) adiacenza.set(String(i), new Set());
  for (const [a, b] of dati) {
    if (!adiacenza.has(a)) adiacenza.set(a, new Set());
    if (!adiacenza.has(b)) adiacenza.set(b, new Set());
    adiacenza.get(a).add(b);
    adiacenza.get(b).add(a);
  }

  const sets = [];
  for (let i = 1; i <= n; i++) {
    const id = String(i);
    const setv = new Set([id, ...adiacenza.get(id)]);

    let found = false;
    for (let k = 0; k < sets.length; k++) {
      const intersecano = [...setv].some((x) => sets[k].has(x));
      if (intersecano) {
        for (const x of setv) sets[k].add(x);
        found = true;
        break;
      }
    }
    if (!found) sets.push(setv);
  }

  return ` ${sets.length - 1}\n`;
}