Bonsoir.

En ce moment j'apprends à implémenter le structure appelée 'arbre' ainsi que les fonctions qui permettent de la parcourir et la manipuler.

On me donne une liste d'arcs ('branches', non-orientées) sous la forme d'une liste de paires de nombres représentant les noeuds aux extrémités des arcs.

Dans un premier temps, j'ai construit, en me servant des ces paires, un réseau sous la forme d'une liste de listes de noeuds et dont l'indice de chacune des listes représente le noeud qui est relié aux différents noeuds de la liste par un arc.

Du coup, mon réseau n'est pas orienté, et en passant d'un numéro dans une liste a la liste dont ce numéro est l'indice, on risque de boucler indéfiniment (ex: l'une des paires reçues est (4, 5), j'ai donc ajouté le noeud 5 à la liste d'indice 4, et le noeud 4 à la liste d'indice 5, si bien que quand je passe du nombre 5 (dans la liste 4) à la liste 5, le nombre 4 qui s'y trouve va me renvoyer à la liste 4, et je vais ainsi faire des allers retours sans fin).

Pour 'orienter' mon réseau (donc pour le transformer en 'arbre') j'ai implémenté une fonction qui, pour une racine donnée, supprime dans chaque liste le nombre qui renvoie du fils au père.

Voici ma fonction d'orientation.

def oriente(reseau,indice):
    for i in reseau[indice]:
        reseau[i].remove(indice)
        oriente(reseau,i)

Le problème, c'est que j'ai utilisé mon code pour un exercice sur France IOI, et il est trop lent (il ne passe que 3 tests sur 10). Je pense que cela est dû au fait qu'avec cette fonction je modifie mon réseau initial, et cela m'oblige à le réinitialiser à chaque étape du programme (à partir d'un réseau que je garde en mémoire dans une variable).

J'imagine que l'on peut faire tout cela plus judicieusement, c.a.d qu'il y a certainement une manière d'obtenir l'équivalent d'un réseau orienté sans modifier réellement le réseau de base. (ou peut-être que je m'y suis carrément mal pris depuis le début, et que je devrais me servir des paires de nombres d'une autre façon pour créer une structure que je puisse orienter à ma guise).

Pour résumer:

1. quelle la meilleure façon de créer un arbre dont je peux définir la racine (et donc l'orientation) à ma guise, à partir d'une liste de paires de noeuds?

2. quelle le meilleure façon de modifier l'orientation d'un arbre?

Quelqu'un peut-il m'aider?

Merci.

Salut,
Dans ton message, tu parles de France IOI. Si on n'a pas l'énoncé, ce sera difficile de t'aider correctement.
Mon avis est qu'un arbre se construit avec un dicctionnaire.
Le premier nombre de la paire est le père ou la clé et tu ajoutes ses fils dans une liste (qui est la valeur).
En parcourant cette liste de valeurs, les nombres devraient être eux-mêmes des clés pour aller plus loin.
Si une des valeurs n'est pas dans la liste des clés, c'est une feuille.

Même construit de cette façon, on n'est pas à l'abri des boucles. Mais c'est seulement s'il y a vraiment une boucle dans le réseau.

Quand on parcours, on "marque" les noeuds qu'on rencontre et si on rencontre un noeud déjà marqué, on est dans une boucle.
En général, les fonctions de parcours des arbres sont récursives.
On connait donc d'une certaine façon le pêre des éléments qu'on parcours.
Pour trouver qui est la racine, c'est un peu plus complexe.
Tu mets le premier élément de chaque paire dans un set.
Tu vérifies que le second est dans le set. Si oui, tu l'enlèves.
À la fin, si tu as plus d'un élément dans ton set, tu as un problème ... tu as plus d'une racine ...
Sinon, tu prend cet élément et c'est lui la racine.

edit: quand je disais que c'était complexe

(1, 2) (2, 3), (3, 1) donnera {1: [2], 2: [3], 3: [1]} avec 2 et 3 dans le set.

Donc, on place tous les premiers dans un set P et tous les second dans un set S

P-S donne ceux qui ne sont pas pointés, donc la ou les racines.

S-P donnera ceux qui ne pointent pas, donc les feuilles

Pour avoir une seule racine, il faut len(P-S) == 1
Je ne suis pas certain de ce que tu veux dire par "orienter" un arbre.
L'arc va toujours du premier élément de la paire vers le second.
Est-ce que tu connais les classes? J'ai déjà codé un arbre binaire avec une classe.
Ça peut sans doute se modifier.

Changer l'orientation d'un arbre peut mener à une absurdité:
-
D = {1: [2, 3], 2: [4, 5], 3: [6, 7]}
N = dict()
for p, L in D.items():
    for i in L:
        if i not in N:
            N[i] = []
        N[i].append(p)
print(N)
-
{2: [1], 3: [1], 4: [2], 5: [2], 6: [3], 7: [3]}

-
Edité par PierrotLeFou 4 mai 2022 à 4:24:40

L'exercice de France IOI se résume à la question suivante (votre attention, svp):

Pour un ensemble donné de paires de noeuds (sous forme de nombres) représentant les arêtes (non orientées: il n'est pas dit quel nombre de la paire est le père et le quel est le fils) d'un réseau, déterminer quel est le noeud (le nombre) qui, pris comme racine du réseau, aura le degrés* maximal de ses fils le moins elevé (par rapport à tout autre choix de racine).

__________

* on appelle degrés d'un noeud dans un graphe le nombre d'arêtes pour lesquelles ce noeud est un sommet.

Pierrot, déjà merci pour tes réponses enrichissantes.

1. Je crois que ce que j'ai fait avec une liste (de listes) est assez proche de ce que tu proposes de faire avec un dictionnaire (je ne vois pas encore ce que le dictionnaire a comme avantage).

2. Peux-tu m'expliquer comment on 'marque' un noeud?

3. Ai-je bien compris? Tu dis qu'il peut y avoir plusieurs racines pour le même arbre?

4. Dans ton exemple (1,2) (2,3) (3,1) le réseau a la forme d'un triangle; pour l'instant, je m'occupe uniquement de graphes simples (qui ne comporte aucune boucle et dont 2 arêtes ne relient jamais la même paire de sommets).

5. Ce que je veux dire par orienter un arbre, c'est que je peux choisir n'importe lequel de ses noeuds pour en être la racine et 'orienter' tous les arcs de l'arbre (déterminer pour chacun d'eux lequel des ses deux sommets sera le père du second) de sorte que tous les autres noeuds se trouvent êtres les descendants de cette racine.

6. Pour le moment je ne cherche pas à 'trouver' la racine de l'arbre mais plutôt à en choisir une, selon le critère de l'énoncé de l'exercice.

7. J'ai lu que l'on peut ramener n'importe quel arbre à un arbre binaire; comment fait-on cela?

8. Je veux bien voir ta classe.

9. Comme tu peux le voir, ma fonction (qui part d'un réseau non orienté où tous les arcs sont représentés dans les 2 sens) détermine une racine au choix. Comme dit, cela m'oblige à stocker en mémoire un réseau non orienté pour pouvoir réinitialiser mon arbre (que la fonction a modifié) et tester le choix d'une nouvelle racine. Y a-t-il un moyen de tester une racine sans modifier réellement le réseau?

Je dois être fatigué ... j'ai de la difficulté à me représenter le problème.
Si on peut choisir n'importe quelle direction pour chaque paire, ça devient vite combinatoire.
En supposant qu'on ait N paires, il y aura 2**N possibilités.
Il serait surprenant qu'elles soient toutes des arbres (voir mon exemple de la fin)
Est-ce que mon dictionnaire peut ressembler à
[[1, 2, 3], [2, 4, 5], [3, 6, 7]]
Le dictionnaire sera plus rapide d'accès.
Il y a plusieurs façons de marquer un noeud.
+ on peut mettre dans un set les noeuds rencontrés
+ dans le noeud lui-même on a une valeur 0 ou 1 qui dit si le noeud est marqué.
Si on doit reculer, il faut effacer les marques.
Si on trouve plusieurs racines, ce n'est justement pas un arbre.
Suppose que quelqu'un te donne ses paires sans te garantir que cela forme un arbre, tu devrais vérifier que s'en est un.
Mon triangle n'est justement pas un arbre car il forme une boucle.
Je ne crois pas qu'on puisse ramener tout arbre à un arbre binaire. Il faut que je vérifie ...
Je te donne le début de ma classe:
class Noeud:
    def __init__(self, val, pere=None):
        self.pere = pere
        self.val = val;
        self.fils = []
        self.flag = False
    def add(self, node):
        noeud = Noeud(node, pere=self)
        self.fils.append(noeud)
...
# Instance d'un noeud
noeud1 = Noeud(1)
noeud1.add(2)

Je pense que les dictionnaires seront plus simples ...

edit encore (j'improvise ...)

Supposons que je construis un dictionnaire des fils de tous les noeuds, chaque noeud d'une paire étant pris comme père à tour de rôle.

Je choisis à tour de rôle toutes les clés comme racine et j'essaie de parcourir le soi-disant arbre en vérifiant que je n'ai pas de boucle.

J'enregistre le meilleur à chaque fois.

L'utilisation des set pour le marquage serait le mieux à mon avis.

J'ai commencé quelques test et considérer les deux directions pour chaque paire cela mène à de drôles de situations.

Ou bien le temps d'exécution sera fou ...

Ou bien j'ai trop de "faux" arbres avec de faux résultats.

J'ai trouvé ceci sur la conversion d'arbre générique en arbre binaire:

https://fr.acervolima.com/convertir-un-arbre-generique-arbre-n-array-en-arbre-binaire/

-
Edité par PierrotLeFou 5 mai 2022 à 5:29:26

10
1 8
3 4
8 3
2 3
2 6
7 6
5 6
5 9
6 0

5

import sys
input = sys.stdin.readline

nbPc = int(input())

# création du réseau non orienté
reseau = [[] for _ in range(nbPc)]
for _ in range(nbPc-1):
    noeud1,noeud2 = map(int,input().split())
    reseau[noeud1].append(noeud2)
    reseau[noeud2].append(noeud1)

# fonction qui oriente le réseau pour un noeud choisi comme racine
def oriente(reseau,noeud):
    for n in reseau[noeud]:
        reseau[n].remove(noeud)
        oriente(reseau,n)

# fonction qui calcule le nombres de descendants d'un noeud
def calculDegres(arbre,noeud):
    if not arbre[noeud]: return 0
    return sum(1+calculDegres(arbre,i) for i in arbre[noeud])

# programme de recherche du noeud optimal pour le connexion de la fibre optique
copie = [i[:] for i in reseau]
compt = 0
maxis = []

for pere in range(nbPc):
    oriente(copie,pere)
    for fils in copie[pere]:
        degNoeud =  calculDegres(copie,fils)
        if degNoeud > compt: compt = degNoeud   
    maxis.append(compt)
    compt = 0
    copie = [i[:] for i in reseau]

print(min(maxis)+1)

-
Edité par Zèbre 5 mai 2022 à 12:33:26

Ça ressemble plus à un problème de flot maximum dans un réseau (mais pas tout à fait).
La différence est que n'importe quel noeud peut être pris comme entrée et n'importe quel comme sortie.
Enfin ce n'est pas tout à fait ça, mais c'est une voie à explorer.
L'énoncé semble nous assurer qu'il n'y a pas de boucle dans le réseau.

Le code suivant fonctionne avec l'exemple donné. Je n'ai aucune idée de son efficacité.

C'est sûrement plus rapide qu'une liste de liste parcourue séquentiellement.

-

# Fonction de parcours en profondeur.
def travel(tree, node):

    if node in marks: return 0

    marks.add(node)
    flow = 0
    for son in tree[node]:
        if son not in marks: flow += 1 + travel(tree, son)
    return flow

    # Ou bien:

    #return sum(travel(tree, son) + 1 for son in tree[node])

# Génération du dictionnaire.
N = int(input())
tree = dict()
for _ in range(N-1):
    p, s = map(int, input().split())
    if p not in tree:
        tree[p] = []
    tree[p].append(s)
    if s not in tree:
       tree[s] = []
    tree[s].append(p)
# Je calcule tous les flots possibles.
itTree = iter(tree.keys())
minLev = N
for node in itTree:
    marks = {node}   # Je coupe le circuit entre ce noeud et les autres.
    # Celui qui aura le maximum le plus bas.
    level = max(travel(tree, son) for son in tree[node])
    if level < minLev:
        minNode = node
        minLev = level
print(minLev + 1)

-

Le code suivant fonctionne également avec l'exemple:

Les tests intermédiaires me montrent que ce sont bien les noeuds 2 et 6 qui sont choisis.

Ce qui te coute le plus cher est la recopie continuelle de ta liste de listes.

-

def travel(tree, node, marks):
    if node in marks: return 0
    marks.add(node)
    return sum(travel(tree, son, marks) + 1 for son in tree[node] if son not in marks)
# Génération du dictionnaire.
N = int(input())
tree = dict()
for _ in range(N-1):
    p, s = map(int, input().split())
    if p not in tree:
        tree[p] = []
    tree[p].append(s)
    if s not in tree:
       tree[s] = []
    tree[s].append(p)
print(min(max(travel(tree, son, {node}) for son in tree[node]) for node in tree) + 1)

-
Edité par PierrotLeFou 6 mai 2022 à 3:54:09

L'utilisation d'un dictionnaire peut prendre plus de place qu'une liste de liste.
L'accès à une clé d'un dicionnaire est plus lent que l'accès à un objet d'une liste.
J'ai donc converti mon code tout en gardant mon idée des set

edit: Un set presque complet est plus grand qu'une liste de booléens équivalente.

L'initialisation d'une liste de booléens est assez rapide et l'accès est très rapide.

Je vais voir comment je pourrais remplacer mon set par cette liste. (ça ne se fait pas en une ligne comme dans le print)
-
def travel(tree, node, marks):
    if node in marks: return 0
    marks.add(node)
    return sum(travel(tree, son, marks)+1 for son in tree[node] if son not in marks)
# Génération du réseau avec liste de listes.
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    p, s = map(int, input().split())
    tree[p].append(s)
    tree[s].append(p)
print(min(max(travel(tree, son, {node}) for son in tree[node]) for node in range(N)) + 1)

-
Edité par PierrotLeFou 6 mai 2022 à 8:09:41

Bonjour.

Je suis peut-être naïf mais de ce que je comprends de l'énoncé c'est que les PC sont en série (y'a un début et une fin) et l'information circule dans les deux sens, j'ai bon ?

Si oui, quelque soit l'endroit où l'on va brancher cette fibre optique, il n'y aura plus de données qui circuleront nulle part.

Je pense que ce n'est pas connecté en ligne mais plus ou moins en étoile.

Et voici ma version avec une liste de booléens:
-
def travel(tree, node, marks):
    if marks[node]: return 0
    marks[node] = True
    return sum(travel(tree, son, marks)+1 for son in tree[node] if not marks[son])
# Génération du réseau avec liste de listes.
N = int(input())
tree = [[] for _ in range(N)];
for _ in range(N-1):
    p, s = map(int, input().split())
    tree[p].append(s)
    tree[s].append(p)
minLevel = N * N
for node in range(N):
    marks = [False] * N
    marks[node] =True
    level = max(travel(tree, son, marks) for son in tree[node])
    if level < minLevel: minLevel = level
print(minLevel+1)

-
Edité par PierrotLeFou 6 mai 2022 à 15:01:02

Bonsoir. (désolé pour mon silence prolongé, je retrouve un peu de temps disponible)

Pierrot, merci. Je suis toujours impressionné par tes codes et ils m'apprennent toujours quelque chose.

Malheureusement, aucun n'est assez rapide aux yeux de France IOI. (3/10 tests validés)

Permets moi une question: Pourquoi dans ton dernier code tu as du faire appel à une variable 'minLevel' et n'as tu pas pu faire, comme dans les codes précédents, une longue opération dans le print ?

CristianoRolando a écrit:

Tu m'as l'air d'avoir un bon niveau parce que tes interrogations sont sensées et rejoignent le design pattern iterator  Ça touche la POO, mais, c'est un DP qui peut être complété avec d'autres DP pas forcément inutile (voir la sectionLien avec les autres patrons)

Merci pour le lien vers ce site intéressant (et pour le compliment, s'il m'était adressé ; bon, il me reste quand même un bon bout de chemin avant de le mériter réellement).

Sais-tu s'il y a moyen de trouver le livre "plongée au coeur des patrons de conceptions" en pdf?

-
Edité par Zèbre 8 mai 2022 à 1:24:41

-
Edité par Zèbre 8 mai 2022 à 1:39:39

Le fait de mettre une valeur entre {...} en fait un set:
>>> a={3}                                                                                                               
>>> type(a)                                                                                                             
<class 'set'>

edit:
J'ai essayé de faire un petit dessin ... du réseau de l'exemple:
|     4   5-9
|     |   |!
| 1-8-3-2-6-0
|         |
|         7
D'après le dessin, le flot maximal se trouve entre 2 et 6.
J'ai parlé de flot maximal au début. Je me demande s'il ne faudrait pas chercher de ce côté?
D'après France IOI, il n'y a qu'un chemin pour passer d'un noeud à un autre. C'est peut-être un indice important.

«Entre 2 PC donnés, il n'existe qu'une seule route possible pour les paquets».

-
Edité par PierrotLeFou 8 mai 2022 à 2:19:30

C'est la quantité maximum d'information que tu peux faire passer par un réseau.
Par exemple, le courant maximum que tu peux faire passer dans un circuit électrique.
Mais je crois que la question devrait plutôt être:
«combien de noeud vont passer par ce cable pour se rendre aux autres?»
Par exemple, si je me rend de 0 à 1, je ne passe pas par 3-4, 6-5, 5-9, 6-7
Et c'est inutile de le faire dans les deux directions, on double seulement l'information pour tout le monde.
Donc, on pourrait faire 0-1, 0-2, ..., 0-9, 1-2, ..., 1-9, ..., 8-9

Si je coupe 2-6, alors 1,8, 3, 4 2 vont continuer à fonctionner d'un côté et 6, 0, 7, 5, 9 de l'autre.

Si je coupe 3-4, seul 4 est isolé, je ne gagne rien à renforcer ce lien avec la fibre optique.

Si je vais de 1 à 2, je passe par 3 et 8, comment ne pas refaire le travail pour les liens 1-3 et 1-8?

Si la théorie des graphes t'intéresse, ce lien s'approche un peu de notre problème:

https://fr.wikipedia.org/wiki/Coupe_minimum

-
Edité par PierrotLeFou 8 mai 2022 à 3:46:12

Moi aussi, j'avais commencé à réfléchir en termes de cables plutôt qu'en termes de noeuds, mais je ne savais pas comment implémenter ce concept et dès que je suis tombé sur la notion de degrés d'un noeud dans un graphe j'ai abandonné l'idée des cables; peut-être à tort...

Peux tu déjà énoncer l'idée en français: qu'est-ce qui rend un cable optimal, est-ce sa position dans le réseau (plus ou moins proche du centre), le nombre de ses frères (les cables qui partgent le même PC que lui), autre chose?

Je ne sais pas trop pour l'instant. Je viens de trouver ceci:

https://fr.wikipedia.org/wiki/Algorithme_de_poussage/r%C3%A9%C3%A9tiquetage

Je n'ai jamais programmé de Push-Relabel, seulement un Ford-Fulkerson qui est plus lent.
Mais si on a 100000 sommets, on ne va pas faire 100000 flow-max?

Si tu regardes le noeud 2, il est directement connecté à peu de noeuds alors que le noeud 6 est connecté à plus de noeuds.

Je pense que c'est plus une question de parcours que de connexions.

edit:
En fait ce que ta fonction calculDegres et ma fonction travel calculent est le nombre de noeuds accessibles par un noeud donné.
Et c'est exactement ce dont on a besoin.
Je me suis demandé si le fait que les arcs sont non orientés ne double pas le travail.
J'ai modifié mon code de telle façon qu'on "isole" vraiment les deux parties du réseau quand on coupe un arc.
Et c'est bien un "arc" et non un "noeud" qu'il faut couper.
Pour cela, on inactive chacun des deux noeuds d'une paire et on cherche le nombre de noeuds accessibles par l'autre.
On prend le maximum des deux et on cherche ensuite le plus petit de tous les maximum.
Ça donne le code suivant:
(j'espère que cela divisera par deux le temps d'exécution ...)

(j'ai encore l'impression qu'on fait des calculs en double ou plus,

et si je considérais les noeuds accessibles par un noeud dans une seule direction ...)
-
def travel(tree, node, marks):
    if node in marks: return  0
    marks.add(node)
    return sum(travel(tree, son, marks)+1 for son in tree[node] if son not in marks)
#
N = int(input())
tree = [[] for _ in range(N)];
for _ in range(N-1):
    p, s = map(int, input().split())
    tree[p].append(s)
    tree[s].append(p)
#
minLevel = N
for node in range(N):
    for son in tree[node]:
        # Je coupe entre le noeud et chacun de ses fils.
        # Je calcule le nombre de noeuds auxquels j'accède de chaque côté de la coupure.
        # Éviter de le faire deux fois pour chaque paire.
        if node < son:
            level = max(travel(tree, node, {son}), travel(tree, son, {node}))
            if level < minLevel: minLevel = level
print(minLevel+1)

-
Edité par PierrotLeFou 8 mai 2022 à 7:48:11

Salut Zebre,

Pour mieux comprendre la notion d'arbre, tu peux regarder sur le site suivant :

http://info-llg.fr/option-mp/pdf/01.arbres.pdf

C'est codé en CamL pour les parties de programme et c'est un peu théorique, mais au moins il y a tout pour comprendre les arbres

Tu "orientes" ton arbre en choisissant une racine et en déterminant les fils des noeuds de ton arbre en utilisant les segments que tu as qui contiennent le noeud en question

Puis, si tu coupes un câble, calculer la longueur |A| du sous-arbre donc la racine est le noeud fils du câble que tu as coupé

La notion d'arbre est récursive, il faut programmer de manière récursive je pense, en faisant attention à limiter le nombre d'appel récursifs pour optimiser la performance temporelle

Bonne journée

Thomatelot

-
Edité par Thomatelot 8 mai 2022 à 10:31:24

Bonjour.

D´après les derniers posts que je viens de lire, j´avais déjà un problème d´interprétation de mon côté. Quand il est dit :

Entre 2 PC donnés, il n'existe qu'une seule route possible pour les paquets.

Je comprenais qu´il y avait un câble unique entre ces deux PC et ne servant qu´à eux. Alors qu´au final, ce câble peut servir au flux de données de plusieurs paires de PC.

PB68 a écrit:

Bonjour.

D´après les derniers posts que je viens de lire, j´avais déjà un problème d´interprétation de mon côté. Quand il est dit :

Entre 2 PC donnés, il n'existe qu'une seule route possible pour les paquets.

Je comprenais qu´il y avait un câble unique entre ces deux PC et ne servant qu´à eux. Alors qu´au final, ce câble peut servir au flux de données de plusieurs paires de PC.

Evidemment ! Deux PC connectés à un même troisième sont connectés entre eux

En effet, ce n'est pas évident de faire un programme suffisamment rapide 

PS : Je ne divulge pas le programme en question pour laisser Zebre chercher encore

-
Edité par Thomatelot 8 mai 2022 à 13:55:02

Je suis toujours convaincu que mon code fait des calculs entrop. Je ne peux pas me connecter à France IOI pour tester.
Et comme je l'ai déjà dit à Zèbre, on ne connait pas le temps que prend notre code.
Le truc auquel je pense pourrait doubler (ou presque) la mémoire.

edit:

Alors si certains ne marchent plus, ça ne s'améliore pas ...

Je vais regarder mes codes précédents pour essayer de comprendre ce que je calcule plus d'une fois.

-
Edité par PierrotLeFou 8 mai 2022 à 14:27:28

Je vais tenter une approche différente, je vous tient au courant si c'est plus performant.

Le principal problème à mon sens est de compter les PC qui n'ont plus accès à Internet lors du débranchement d'un câble.

Il faut faire en sorte de ne pas le calculer plusieurs fois pour un même câble débranché.

Mon idée était de calculer une seule fois le nombre de PC à "droite" d'un câble, pour chaque câble de la forme :

(noeud1, noeud2), donc noeud2 et les noeuds qui y sont connectés même indirectement mais sans passer par le noeud1 et en remarquant le nombre de PC à "gauche" du câble vaut N - nb_PC_droite

Malheureusement, ce n'est pas encore la solution, je ne réussis que les 3 premiers tests au niveau de la limite de temps...

-
Edité par Thomatelot 8 mai 2022 à 15:22:06

Si un cable est débranché, on coupe le réseau en deux sous-réseaux (parfois vide).
Lequel n'a plus accès à Internet?

Je viens de dire que je crois que certains calculs sont fait plus d'une fois.

Sauf qu'il faudra les sauver quelque part.

J'ai déjà la liste des noeuds connectés à chaque noeud.

Je sais que la somme des longueurs de ces sous-listes est le nombre de connexions.

Je sais qu'il n'y a qu'un chemin pour me rendre d'un noeud à un autre.

Si j'associais à chaque noeud de la sous-liste le nombre de noeud acccessibles exclusivement par ce lien, le calcul serait déjà plus facile.

Il faut faire la récursion jusqu'aux noeuds de fin de course et propager les résultats en revenant de la récursion à chaque niveau.

Facile à dire, mais pas fait ...

Par exemple pour le noeud 2:
[[3, 0], [6, 0]] au départ et les 0 sont remplacés par les valeurs calculées.

Ça devrait doner  [[3, 4], [6, 5]] à la fin pour le noeud 2.

Pour le noeud 6, ça devrait donner [[0, 1], [2, 5], [5, 2], [7, 1]]

On fait la somme des nombre d'accès et on soustrait alternativement celui dont on ne veut pas.

En fait cette somme est toujours N, le nombre total de connexions.

edit:
Je suis revenu à un dictionnaire de dictionaires pour plus de rapidité dans les deux directions.
J'ose croire que je ne dépasserai pas la limite de mémoire.
La façon dont j'ai modifié ma foncion travel() est telle qu'elle a tendance à se propager vers les extrémités du réseau.
Elle ramène vers le point de départ les informations sur le nombre de noeuds de chaque côté d'un arc.
Les valeurs sont complémentaires de chaque côté de l'arc.
De cette façon, je ne parcours le réseau de façon récursive qu'une seule fois.
Je rappelle qu'il n'y a qu'un seul chemin d'un noeud à tout autre.
En bloquant le retour, je peux me passer des marques sans boucler.
Je n'ai plus besoin d'ajouter 1 au minimum.
-
def travel(tree, node):
    total = 0
    for son, access in tree[node].items():
        if access == 0:
            tree[son][node] = -1   # Bloquer le retour.
            access = travel(tree, son)
            total += access
            tree[node][son] = access
            tree[son][node] = N - access
    return total+1
N = int(input())
tree = {i: {} for i in range(N)}
for _ in range(N-1):
    p, s = map(int, input().split())
    tree[p][s] = 0
    tree[s][p] = 0
total =travel(tree, 0)
print(min(max(access, N-access) for node in range(N) for son , access in tree[node].items()))

-
Edité par PierrotLeFou 9 mai 2022 à 7:50:12

Les deux dernières lignes peuvent être remplacées par:

travel(tree, 0)
print(min(max(access, N-access) for node in range(N) for access in tree[node].values()))

On ne garde pas la valeur de  retour de travel. Je remplace .items par .values car je n'ai pas besoin de la clé ici.

-
Edité par PierrotLeFou 9 mai 2022 à 18:40:12

Désolé Pierrot, 3 réponses incorrectes, 2 accès hors mémoires et 5 dépassements du temps imparti...

2

1

-
Edité par Zèbre 10 mai 2022 à 0:15:13

Je l'ai déjà dit, on n'a pas leurs données pour se corriger.
Je n'ai que l'exemple du début pour tester. C'est bien peu.
Dans le cas où on a 100000 noeuds, je me doutais un peu que j'étais près de la limite de mémoire.

Ça pourrait marcher avec une liste de dictionnaires:

>>> from sys import getsizeof                                                                                           
>>> d={i:dict() for i in range(100000)}                                                                                 
>>> getsizeof(d)                                                                                                        
5242968                                                                                                                 
>>> l=[[] for i in range(100000)]                                                                                       
>>> getsizeof(l)                                                                                                        
800984                                                                                                                  
>>> l=[dict() for i in range(100000)]                                                                                   
>>> getsizeof(l)                                                                                                        
800984                                                                                                                  
>>>                                                                                                                     
Pour les résultats incorrects, c'est peut être un réseau assez tordu.
L'algorithme en soi devrait être assez rapide car le nombre de parcours récursifs se limite à un seul appel de base.
Je ne fais pas deux fois le même travail.

Une liste de dictionnaires serait légèrement plus rapide et prendrait moins de place.

Ça ne m'avance pas beaucoup si je ne sais pas dans quels cas ¸ça ne marche pas.

La modification se limite à la ligne suivante:

tree = [{} for i in range(N)]

As-tu un autre exemple corrigé à ta disposition?

Je trouve toujours l'énoncé difficile à interpréter.
Ici, on a 5 noeuds de chaque côté du lien 2-6 et on a 10 noeuds.
La réponse est-elle 5, ou 10-5 ... ?
Pour le réseau  0-1-2, j'aurai au maximum 1 noeud isolé.
La contrainte dit:
• 1 <= N <= 100 000
Donc N peut être égal à 1. On est censé retourner quoi dans ce cas? 0?
J'aurais:  if N <= 1: tree = [{0: 0}]
Je propose ce qui suit comme modification pour le print:
print(N - min(max(access, N-access) for node in range(N) for access in tree[node].values()))

-
Edité par PierrotLeFou 10 mai 2022 à 3:33:33

-
Edité par Zèbre 10 mai 2022 à 11:00:02

Et je ne sais pas si ceux qui ont planté pour cause de mémoire ou de temps limite auraient donné un bon résultat ...
Est-ce qu'il y a une structure en Python que je ne connais pas? Et qui me permet d'accéder aux deux  directions d'un arc rapidement?
Je vais regarder du côté des classes pour voir si je peux construire un vrai graphe.

Pour un graphe, j'aurais besoin de deux type d'objets:
+ les noeuds
  identificateur
  liste des arcs connectés
  flag pour le parcours
+ les arcs:
   noeud "gauche"
   noeud "droit"
 flot (dans une direction seule, car c'est le complément dans l'autre)
Dans notre problème on aura au total N noeuds et N-1 arcs.
Il faudra savoir ce que ça représente comme mémoire.
Mon algorithme de propagation (travel) serait-il plus efficace avec les classes?
Comment vais-je récupérer les résultats?
Puis-je ramener le résultat attendu durant le parcours plutôt qu'à la fin?

edit: hé oui ...
J'ai refait mon code avec des classes. C'est pas tout à fait POO, mais ça marche.
Reste à savoir si France IOI va accepter ...
-
class Node:
    def __init__(self):
        self.arrows = []
    def add(self, node):
        arrow = Arrow(self, node)
        self.arrows.append(arrow)
        node.arrows.append(arrow)
#
class Arrow:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        self.flow = 0
#
def travel(node):
    total = 0
    for arrow in node.arrows:
        if arrow.flow == 0:
            arrow.flow = -1
            son = arrow.right
            if son == node: son = arrow.left
            arrow.flow = access = travel(son)
            total += access
    return total + 1
#
N = int(input())
nodes = [Node() for i in range(N)]
for _ in range(N-1):
    p, s = map(int, input().split())
    nodes[p].add(nodes[s])
if N <= 1: nodes[0].add(nodes[0])
travel(nodes[0])
#
minFlow = N
for node in nodes:
     for arrow in node.arrows:
        flow = arrow.flow
        flow = max(flow, N-flow)
        if flow < minFlow: minFlow = flow
print(N - minFlow)

-
Edité par PierrotLeFou 11 mai 2022 à 4:45:13