Vous avez N ordinateurs et [Ca, Cb] signifie que a est connecté à b et que cette connectivité est symétrique et transitive. Le problème est d'écrire un programme qui vérifie que tous les ordinateurs sont interconnectés et se parlent entre eux.Problème de théorie des réseaux et des graphes
Un algorithme efficace dans le temps est préférable.
Ceci est appelé Graph Connectivity. Lisez à ce sujet et vous pouvez résoudre votre problème.
Toute recherche du graphique qui ne traverse pas plusieurs fois un nœud devrait être suffisante. Il y a beaucoup d'options: http://www.algorithmist.com/index.php/Graph_Connectivity Je choisirais probablement DFS ou BFS.
parce que vous dites que le temps algorithme efficace est preferable.thus DFS est le meilleur algorithme pour U..notice que la taille de votre bord dans l'ordinateur de réseau est petit DSF: http://en.wikipedia.org/wiki/Depth-first_search
remarque: la taille de votre bord dans l'ordinateur du réseau est petite –
Vous devez marquer ceci comme devoirs –
@Tristram: Je l'ai signalé 'possible-devoirs' pour lui ... –
@SIVA, qu'avez-vous fait pour résoudre le problème, et quels problèmes avez-vous avec votre solution? – atk