Znajdowanie wszystkich cykli na ukierunkowanym wykresie

Jak mogę znaleźć (powtórzyć) WSZYSTKIE cykle na ukierunkowanym wykresie z / do danego węzła?

Na przykład chcę coś takiego:

A->B->A
A->B->C->A

ale nie: B-> C-> B

Znalazłem tę stronę podczas wyszukiwania, a ponieważ cykle nie są takie same jak silnie połączone komponenty, szukałem dalej i wreszcie znalazłem skuteczny algorytm, który wyświetla wszystkie (elementarne) cykle ukierunkowanego wykresu. Pochodzi od Donalda B. Johnsona, a artykuł można znaleźć pod następującym linkiem:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Implementację Java można znaleźć w:

http://normalisiert.de/code/java/elementaryCycles.zip

Mathematica demonstracja Algorytm Johnsona można znaleźć tutaj , realizacja można pobrać z prawej strony ( „Pobierz kod autor” ).

Uwaga: w rzeczywistości istnieje wiele algorytmów dla tego problemu. Niektóre z nich są wymienione w tym artykule:

http://dx.doi.org/10.1137/0205007

Według artykułu algorytm Johnsona jest najszybszy.

Tu powinno działać pierwsze wyszukiwanie głębokości z cofaniem. Zachowaj tablicę wartości logicznych, aby śledzić, czy odwiedziłeś wcześniej węzeł. Jeśli zabraknie Ci nowych węzłów, do których chcesz się udać (bez uderzania w węzeł, w którym już byłeś), po prostu cofnij się i wypróbuj inną gałąź.

System plików DFS jest łatwy do wdrożenia, jeśli masz listę sąsiadów do reprezentowania wykresu. Na przykład przym. [A] = {B, C} wskazuje, że B i C są dziećmi A.

Na przykład pseudo-kod poniżej. „start” to węzeł, od którego zaczynasz.

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

Wywołaj powyższą funkcję z węzłem początkowym:

visited = {}
dfs(adj,start,visited)

Po pierwsze - tak naprawdę nie chcesz próbować znaleźć dosłownie wszystkich cykli, ponieważ jeśli jest 1, to jest ich nieskończona liczba. Na przykład ABA, ABABA itp. Lub może być możliwe połączenie 2 cykli w 8-podobny cykl itp. Itp. Znaczącym podejściem jest poszukiwanie wszystkich tak zwanych prostych cykli - tych, które się nie krzyżują, z wyjątkiem w punkcie początkowym / końcowym. Następnie, jeśli chcesz, możesz wygenerować kombinację prostych cykli.

Jednym z podstawowych algorytmów znajdowania wszystkich prostych cykli na ukierunkowanym wykresie jest: Przeprowadź najpierw głębokość wszystkich prostych ścieżek (tych, które się nie krzyżują) na wykresie. Za każdym razem, gdy bieżący węzeł ma następcę na stosie, wykrywany jest prosty cykl. Składa się z elementów na stosie, zaczynając od zidentyfikowanego następcy i kończąc na górze stosu. Pierwsze przejście głębokości wszystkich prostych ścieżek jest podobne do pierwszego wyszukiwania głębokości, ale nie oznacza się / nie zapisuje odwiedzonych węzłów innych niż aktualnie na stosie jako punktów zatrzymania.

Powyższy algorytm brutalnej siły jest wyjątkowo nieefektywny, a ponadto generuje wiele kopii cykli. Jest to jednak punkt wyjścia wielu praktycznych algorytmów, które stosują różne ulepszenia w celu poprawy wydajności i uniknięcia powielania cyklu. Byłem zaskoczony, gdy jakiś czas temu dowiedziałem się, że te algorytmy nie są łatwo dostępne w podręcznikach i Internecie. Zrobiłem więc badania i wdrożyłem 4 takie algorytmy i 1 algorytm dla cykli w niekierowanych grafach w bibliotece Java typu open source tutaj: http://code.google.com/p/niographs/ .

BTW, ponieważ wspomniałem o grafach bezkierunkowych: algorytm dla nich jest inny. Zbuduj drzewo rozpinające, a następnie każda krawędź, która nie jest częścią drzewa, tworzy prosty cykl wraz z pewnymi krawędziami w drzewie. Znalezione w ten sposób cykle tworzą tzw. Podstawę cyklu. Wszystkie proste cykle można następnie znaleźć, łącząc 2 lub więcej odrębnych cykli podstawowych. Aby uzyskać więcej informacji, patrz np. To: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Najprostszym wyborem, jaki znalazłem, aby rozwiązać ten problem, było użycie biblioteki python o nazwie networkx.

Implementuje algorytm Johnsona wymieniony w najlepszej odpowiedzi na to pytanie, ale jego wykonanie jest dość proste.

W skrócie potrzebujesz:

import networkx as nx
import matplotlib.pyplot as plt

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])

# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])

#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))

Odpowiedź: [[„a”, „b”, „d”, „e”], [„a”, „b”, „c”]]

W celu wyjaśnienia:

1. Silnie połączone komponenty znajdą wszystkie podgrafy, które mają co najmniej jeden cykl, a nie wszystkie możliwe cykle na wykresie. np. jeśli weźmiesz wszystkie silnie połączone komponenty i zwiniesz / grupujesz / scalisz każdy z nich w jeden węzeł (tj. węzeł na komponent), otrzymasz drzewo bez cykli (właściwie DAG). Każdy element (który jest zasadniczo podgraphem z co najmniej jednym cyklem) może zawierać o wiele więcej możliwych cykli wewnętrznie, więc SCC NIE znajdzie wszystkich możliwych cykli, znajdzie wszystkie możliwe grupy, które mają co najmniej jeden cykl, a jeśli zgrupujesz je, wtedy wykres nie będzie miał cykli.

2. aby znaleźć wszystkie proste cykle na wykresie, jak wspomniano inni, algorytm Johnsona jest kandydatem.

Raz otrzymałem to pytanie do wywiadu. Podejrzewam, że tak się stało. Przybywasz tutaj po pomoc. Podziel problem na trzy pytania, a stanie się to łatwiejsze.

1. jak ustalić następną prawidłową trasę
2. jak ustalić, czy punkt został użyty
3. jak uniknąć ponownego przekroczenia tego samego punktu

Problem 1) Użyj wzorca iteratora, aby zapewnić sposób iteracji wyników trasy. Dobrym miejscem na umieszczenie logiki w celu uzyskania następnej trasy jest prawdopodobnie „moveNext” iteratora. Aby znaleźć prawidłową trasę, zależy to od struktury danych. Dla mnie była to tabela sql pełna ważnych możliwości tras, więc musiałem zbudować zapytanie, aby uzyskać prawidłowe miejsca docelowe podane jako źródło.

Problem 2) Wciśnij każdy węzeł, gdy znajdziesz je w kolekcję, gdy je dostaniesz, oznacza to, że możesz bardzo łatwo „podwoić się” o jeden punkt, sprawdzając kolekcję, którą budujesz w locie.

Problem 3) Jeśli w którymkolwiek momencie zauważysz, że podwajasz się, możesz usunąć rzeczy z kolekcji i „wykonać kopię zapasową”. Następnie od tego momentu spróbuj ponownie „przejść do przodu”.

Hack: jeśli używasz Sql Server 2008, istnieje kilka nowych „hierarchii” rzeczy, których możesz użyć, aby szybko rozwiązać ten problem, jeśli ustrukturyzujesz swoje dane w drzewie.

Warianty oparte na DFS z tylnymi krawędziami rzeczywiście znajdą cykle, ale w wielu przypadkach NIE będą minimalne cykle . Ogólnie DFS daje ci flagę informującą, że istnieje cykl, ale nie jest wystarczająco dobry, aby znaleźć cykle. Na przykład wyobraź sobie 5 różnych cykli dzielących dwie krawędzie. Nie ma prostego sposobu na identyfikację cykli przy użyciu samego DFS (w tym wariantów cofania).

Algorytm Johnsona faktycznie daje wszystkie unikalne proste cykle i ma dobrą złożoność czasu i przestrzeni.

Ale jeśli chcesz po prostu znaleźć cykle MINIMALNE (co oznacza, że ​​może być więcej niż jeden cykl przechodzący przez dowolny wierzchołek, a my jesteśmy zainteresowani znalezieniem minimalnych cykli) ORAZ twój wykres nie jest bardzo duży, możesz spróbować użyć prostej metody poniżej. Jest to BARDZO proste, ale raczej powolne w porównaniu do Johnsona.

Więc jeden z absolutnie najłatwiejszych sposobów na znalezienie cykli MINIMALNYCH jest użycie algorytmu Floyda do znalezienia minimalnych ścieżek między wszystkimi wierzchołkami za pomocą macierzy przyległości. Algorytm ten nie jest tak optymalny jak Johnson, ale jest tak prosty, a jego wewnętrzna pętla jest tak ścisła, że ​​w przypadku mniejszych wykresów (<= 50-100 węzłów) absolutnie sensowne jest jego użycie. Złożoność czasu wynosi O (n ^ 3), złożoność przestrzeni O (n ^ 2), jeśli korzystasz ze śledzenia rodzica, i O (1), jeśli nie. Przede wszystkim znajdźmy odpowiedź na pytanie, czy istnieje cykl. Algorytm jest bardzo prosty. Poniżej znajduje się fragment kodu w Scali.

  val NO_EDGE = Integer.MAX_VALUE / 2

  def shortestPath(weights: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        weights(i)(j) = throughK
      }
    }
  }

Pierwotnie ten algorytm działa na wykresie ważonym, aby znaleźć wszystkie najkrótsze ścieżki między wszystkimi parami węzłów (stąd argument wag). Aby działało poprawnie, musisz podać 1, jeśli między węzłami istnieje ukierunkowana krawędź lub w przeciwnym razie NIE_EDGE. Po wykonaniu algorytmu można sprawdzić główną przekątną, jeśli istnieją wartości mniejsze niż NO_EDGE, niż ten węzeł uczestniczy w cyklu o długości równej wartości. Każdy inny węzeł tego samego cyklu będzie miał tę samą wartość (na głównej przekątnej).

Aby zrekonstruować sam cykl, musimy użyć nieco zmodyfikowanej wersji algorytmu ze śledzeniem rodziców.

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = k
        weights(i)(j) = throughK
      }
    }
  }

Macierz rodzicielska początkowo powinna zawierać źródłowy indeks wierzchołków w komórce krawędzi, jeśli istnieje krawędź między wierzchołkami, a w przeciwnym razie -1. Po powrocie funkcji dla każdej krawędzi będziesz mieć odniesienie do węzła nadrzędnego w najkrótszym drzewie ścieżek. A potem łatwo jest odzyskać rzeczywiste cykle.

W sumie mamy następujący program, aby znaleźć wszystkie minimalne cykle

  val NO_EDGE = Integer.MAX_VALUE / 2;

  def shortestPathWithParentTracking(
         weights: Array[Array[Int]],
         parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = parents(i)(k)
        weights(i)(j) = throughK
      }
    }
  }

  def recoverCycles(
         cycleNodes: Seq[Int], 
         parents: Array[Array[Int]]): Set[Seq[Int]] = {
    val res = new mutable.HashSet[Seq[Int]]()
    for (node <- cycleNodes) {
      var cycle = new mutable.ArrayBuffer[Int]()
      cycle += node
      var other = parents(node)(node)
      do {
        cycle += other
        other = parents(other)(node)
      } while(other != node)
      res += cycle.sorted
    }
    res.toSet
  }

i mała główna metoda tylko po to, by przetestować wynik

  def main(args: Array[String]): Unit = {
    val n = 3
    val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
    val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
    shortestPathWithParentTracking(weights, parents)
    val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
    val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
    println("The following minimal cycle found:")
    cycles.foreach(c => println(c.mkString))
    println(s"Total: ${cycles.size} cycle found")
  }

i wynik jest

The following minimal cycle found:
012
Total: 1 cycle found

W przypadku niekierowanego wykresu niedawno opublikowany artykuł ( Optymalna lista cykli i ścieżek st w niekierowanych grafach ) oferuje optymalne asymptotycznie rozwiązanie. Możesz go przeczytać tutaj http://arxiv.org/abs/1205.2766 lub tutaj http://dl.acm.org/citation.cfm?id=2627951 Wiem, że to nie odpowiada na twoje pytanie, ale od tytułu Twoje pytanie nie wspomina o kierunku, może być nadal przydatne w wyszukiwarce Google

Zacznij od węzła X i sprawdź wszystkie węzły podrzędne (węzły nadrzędne i podrzędne są równoważne, jeśli nie są przekierowane). Zaznacz te węzły potomne jako dzieci X. Z dowolnego takiego węzła potomnego A zaznacz, że są dziećmi potomków A, X ', gdzie X' jest oznaczony jako 2 kroki dalej.). Jeśli później naciśniesz X i oznaczysz go jako dziecko X '', oznacza to, że X jest w cyklu 3-węzłowym. Cofanie do rodzica jest łatwe (tak jak jest, algorytm nie obsługuje tego, więc można znaleźć którykolwiek rodzic ma X ').

Uwaga: Jeśli wykres nie jest przekierowany lub ma jakiekolwiek dwukierunkowe krawędzie, algorytm ten staje się bardziej skomplikowany, zakładając, że nie chcesz przesuwać tej samej krawędzi dwa razy w cyklu.

Jeśli chcesz znaleźć wszystkie obwody elementarne na wykresie, możesz użyć algorytmu EC autorstwa JAMES C. TIERNAN, znalezionego na papierze od 1970 roku.

Bardzo oryginalny algorytm WE jak udało mi się wdrożyć go w php (nadzieja nie ma żadnych błędów znajduje się poniżej). Może również znaleźć pętle, jeśli takie istnieją. Obwody w tej implementacji (które próbują sklonować oryginał) są elementami niezerowymi. Zero tutaj oznacza nieistnienie (zero, jakie znamy).

Poza tym poniżej podano inną implementację, która daje algorytmowi większą niezależność, co oznacza, że ​​węzły mogą zaczynać się z dowolnego miejsca, nawet od liczb ujemnych, np. -4, -3, -2, itp.

W obu przypadkach wymagane jest, aby węzły były sekwencyjne.

Być może będziesz musiał przestudiować oryginalny artykuł, James C. Tiernan Elementary Circuit Algorytm

<?php
echo  "<pre><br><br>";

$G = array(
        1=>array(1,2,3),
        2=>array(1,2,3),
        3=>array(1,2,3)
);


define('N',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();


#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
    if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
    $k++;
    $P[$k] = $child;
    goto EC2_Path_Extension;
}   }

#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle
    $Circ[] = $P;
}

#[EC4 Vertex Closure]
if($k===1){
    goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
    if( $H[$P[$k-1]][$m]===0 ){
        $H[$P[$k-1]][$m]=$P[$k];
        break(1);
    }
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
    $H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
    goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
        1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>

to jest druga implementacja, bardziej niezależna od wykresu, bez goto i bez wartości tablic, zamiast tego używa kluczy tablic, ścieżka, wykres i obwody są przechowywane jako klucze tablic (użyj wartości tablic, jeśli chcesz, po prostu zmień wymagane linie). Przykładowy wykres zaczyna się od -4, aby pokazać jego niezależność.

<?php

$G = array(
        -4=>array(-4=>true,-3=>true,-2=>true),
        -3=>array(-4=>true,-3=>true,-2=>true),
        -2=>array(-4=>true,-3=>true,-2=>true)
);


$C = array();


EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){

    $CNST_not_closed =  false;                          // this flag indicates no closure
    $CNST_closed        = true;                         // this flag indicates closure
    // define the state where there is no closures for some node
    $tmp_first_node  =  key($G);                        // first node = first key
    $tmp_last_node  =   $tmp_first_node-1+count($G);    // last node  = last  key
    $CNST_closure_reset = array();
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $CNST_closure_reset[$k] = $CNST_not_closed;
    }
    // define the state where there is no closure for all nodes
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $H[$k] = $CNST_closure_reset;   // Key in the closure arrays represent nodes
    }
    unset($tmp_first_node);
    unset($tmp_last_node);


    # Start algorithm
    foreach($G as $init_node => $children){#[Jump to initial node set]
        #[Initial Node Set]
        $P = array();                   // declare at starup, remove the old $init_node from path on loop
        $P[$init_node]=true;            // the first key in P is always the new initial node
        $k=$init_node;                  // update the current node
                                        // On loop H[old_init_node] is not cleared cause is never checked again
        do{#Path 1,3,7,4 jump here to extend father 7
            do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
                $new_expansion = false;
                foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
                    if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
                        $P[$child]=true;    // add this child to the path
                        $k = $child;        // update the current node
                        $new_expansion=true;// set the flag for expanding the child of k
                        break(1);           // we are done, one child at a time
            }   }   }while(($new_expansion===true));// Do while a new child has been added to the path

            # If the first node is child of the last we have a circuit
            if( isset($G[$k][$init_node])===true ){
                $C[] = $P;  // Leaving this out of closure will catch loops to
            }

            # Closure
            if($k>$init_node){                  //if k>init_node then alwaya count(P)>1, so proceed to closure
                $new_expansion=true;            // $new_expansion is never true, set true to expand father of k
                unset($P[$k]);                  // remove k from path
                end($P); $k_father = key($P);   // get father of k
                $H[$k_father][$k]=$CNST_closed; // mark k as closed
                $H[$k] = $CNST_closure_reset;   // reset k closure
                $k = $k_father;                 // update k
        }   } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
        // Advance Initial Vertex Context
    }//foreach initial


}//function

?>

Przeanalizowałem i udokumentowałem EC, ale niestety dokumentacja jest w języku greckim.

Istnieją dwa etapy (algorytmy) związane ze znalezieniem wszystkich cykli w DAG.

Pierwszym krokiem jest użycie algorytmu Tarjana do znalezienia zestawu silnie połączonych komponentów.

1. Zacznij od dowolnego dowolnego wierzchołka.
2. DFS z tego wierzchołka. Dla każdego węzła x zachowaj dwie liczby: dfs_index [x] i dfs_lowval [x]. dfs_index [x] przechowuje dane, kiedy odwiedzany jest ten węzeł, natomiast dfs_lowval [x] = min (dfs_low [k]) gdzie k jest wszystkimi potomkami x, które nie są bezpośrednio rodzicem x w drzewie rozpinającym dfs.
3. Wszystkie węzły z tym samym dfs_lowval [x] znajdują się w tym samym silnie połączonym komponencie.

Drugim krokiem jest znalezienie cykli (ścieżek) w połączonych komponentach. Moją sugestią jest użycie zmodyfikowanej wersji algorytmu Hierholzera.

Chodzi o to:

1. Wybierz dowolny początkowy wierzchołek v i podążaj śladem krawędzi od tego wierzchołka, aż wrócisz do v. Nie można utknąć na żadnym innym wierzchołku niż v, ponieważ równy stopień wszystkich wierzchołków gwarantuje, że gdy szlak wejdzie na inny wierzchołek w musi pozostawać niewykorzystaną krawędzią, pozostawiając w. Utworzona w ten sposób trasa jest trasą zamkniętą, ale może nie obejmować wszystkich wierzchołków i krawędzi początkowego wykresu.
2. Tak długo, jak istnieje wierzchołek v, który należy do bieżącej trasy, ale ma sąsiadujące krawędzie nie będące częścią trasy, rozpocznij kolejną ścieżkę od v, podążając za niewykorzystanymi krawędziami, aż wrócisz do v, i dołącz do trasy utworzonej w ten sposób do poprzednia trasa.

Oto link do implementacji Java z przypadkiem testowym:

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

Natknąłem się na następujący algorytm, który wydaje się być bardziej wydajny niż algorytm Johnsona (przynajmniej w przypadku większych wykresów). Nie jestem jednak pewien jego wydajności w porównaniu z algorytmem Tarjana.
Dodatkowo, jak dotąd sprawdziłem tylko trójkąty. W razie zainteresowania zobacz „Arboricity and Subgraph Listing Algorytmy” Norishige Chiby i Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

Rozwiązanie JavaScript wykorzystujące listy rozłączne połączone. Można zaktualizować do rozłącznych lasów, aby skrócić czas działania.

var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}

//MIT license, authored by Ling Qing Meng

//'4\nYYNN\nYYYN\nNYYN\nNNNY'

//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
    adjMatrix.push(reformat[i]);
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
    var s = new LinkedList();
    s.add(i);
    sets.push(s);
}

//populate friend potentials using combinatorics, then filters
var people =  [];
var friends = [];
for (var i = 0; i < N; i++) {
    people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
    if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
        friends.push(potentialFriends[i]);
    }
}


//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
    var x = friends[i][0];
    var y = friends[i][1];
    if (FindSet(x) != FindSet(y)) {
        sets.push(MergeSet(x,y));
    }
}


for (var i = 0; i < sets.length; i++) {
    //sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);



//Linked List data structures neccesary for above to work
function Node(){
    this.data = null;
    this.next = null;
}

function LinkedList(){
    this.head = null;
    this.tail = null;
    this.size = 0;

    // Add node to the end
    this.add = function(data){
        var node = new Node();
        node.data = data;
        if (this.head == null){
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    };


    this.contains = function(data) {
        if (this.head.data === data) 
            return this;
        var next = this.head.next;
        while (next !== null) {
            if (next.data === data) {
                return this;
            }
            next = next.next;
        }
        return null;
    };

    this.traverse = function() {
        var current = this.head;
        var toPrint = '';
        while (current !== null) {
            //callback.call(this, current); put callback as an argument to top function
            toPrint += current.data.toString() + ' ';
            current = current.next; 
        }
        console.log('list data: ',toPrint);
    }

    this.merge = function(list) {
        var current = this.head;
        var next = current.next;
        while (next !== null) {
            current = next;
            next = next.next;
        }
        current.next = list.head;
        this.size += list.size;
        return this;
    };

    this.reverse = function() {
      if (this.head == null) 
        return;
      if (this.head.next == null) 
        return;

      var currentNode = this.head;
      var nextNode = this.head.next;
      var prevNode = this.head;
      this.head.next = null;
      while (nextNode != null) {
        currentNode = nextNode;
        nextNode = currentNode.next;
        currentNode.next = prevNode;
        prevNode = currentNode;
      }
      this.head = currentNode;
      return this;
    }


}


/**
 * GENERAL HELPER FUNCTIONS
 */

function FindSet(x) {
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            return sets[i].contains(x);
        }
    }
    return null;
}

function MergeSet(x,y) {
    var listA,listB;
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            listA = sets[i].contains(x);
            sets.splice(i,1);
        }
    }
    for (var i = 0; i < sets.length; i++) {
        if (sets[i].contains(y) != null) {
            listB = sets[i].contains(y);
            sets.splice(i,1);
        }
    }
    var res = MergeLists(listA,listB);
    return res;

}


function MergeLists(listA, listB) {
    var listC = new LinkedList();
    listA.merge(listB);
    listC = listA;
    return listC;
}

//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
    return matrix[pair[0]].charAt(pair[1]);
}

function k_combinations(set, k) {
    var i, j, combs, head, tailcombs;
    if (k > set.length || k <= 0) {
        return [];
    }
    if (k == set.length) {
        return [set];
    }
    if (k == 1) {
        combs = [];
        for (i = 0; i < set.length; i++) {
            combs.push([set[i]]);
        }
        return combs;
    }
    // Assert {1 < k < set.length}
    combs = [];
    for (i = 0; i < set.length - k + 1; i++) {
        head = set.slice(i, i+1);
        tailcombs = k_combinations(set.slice(i + 1), k - 1);
        for (j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
}

DFS z węzłów początkowych, śledź ścieżkę DFS podczas przechodzenia i zapisz ścieżkę, jeśli znajdziesz krawędź z węzła v w ścieżce do s. (v, s) jest back-edge w drzewie DFS, a zatem wskazuje cykl zawierający s.

Jeśli chodzi o pytanie dotyczące cyklu permutacji , przeczytaj więcej tutaj: https://www.codechef.com/problems/PCYCLE

Możesz wypróbować ten kod (wprowadź rozmiar i liczbę cyfr):

# include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int num[1000];
    int visited[1000]={0};
    int vindex[2000];
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int t_visited=0;
    int cycles=0;
    int start=0, index;

    while(t_visited < n)
    {
        for(int i=1;i<=n;i++)
        {
            if(visited[i]==0)
            {
                vindex[start]=i;
                visited[i]=1;
                t_visited++;
                index=start;
                break;
            }
        }
        while(true)
        {
            index++;
            vindex[index]=num[vindex[index-1]];

            if(vindex[index]==vindex[start])
                break;
            visited[vindex[index]]=1;
            t_visited++;
        }
        vindex[++index]=0;
        start=index+1;
        cycles++;
    }

    printf("%d\n",cycles,vindex[0]);

    for(int i=0;i<(n+2*cycles);i++)
    {
        if(vindex[i]==0)
            printf("\n");
        else
            printf("%d ",vindex[i]);
    }
}

Wersja DFS c ++ dla pseudokodu w odpowiedzi drugiego piętra:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}