ग्राफ में सभी चक्र खोजें, redux

Question

मुझे पता है कि इस प्रश्न पर कुछ जवाब मौजूद हैं। हालांकि, मैंने पाया कि उनमें से कोई भी वास्तव में इस बिंदु पर नहीं ला रहा है।
कुछ लोगों का तर्क है कि एक चक्र (लगभग) एक प्रभावशाली तरीके से कनेक्ट घटकों (रों। Finding all cycles in a directed graph) के रूप में ही है, तो एक ही है कि लक्ष्य के लिए बनाया गया एल्गोरिदम का उपयोग कर सकता है।
कुछ लोगों का तर्क है कि एक चक्र डीएफएस के माध्यम से किया जा सकता है खोजने और बैक-किनारों के लिए जाँच (रों। फ़ाइल निर्भरता पर ग्राफ प्रलेखन को बढ़ावा देने)।

अब मैं पर चक्रों में कुछ ग्राफों को डीएफएस के माध्यम से पहचाना जा सकता है और बैक-एज की जांच कर सकता हूं?
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf (एसओ पर यहां पाया गया) चक्र अड्डों पर आधारित एक मेथोड बताता है। मुझे व्यक्तिगत रूप से, मुझे यह बहुत सहज नहीं लगता है इसलिए मैं एक अलग समाधान की तलाश में हूं।

संपादित करें: मेरी प्रारंभिक राय जाहिरा तौर पर गलत था। एस "मॉरन" द्वारा अगला जवाब।
प्रारंभिक राय: मेरे राय है कि यह वास्तव में डीएफएस-VISIT के रूप में इस तरह काम कर सकता था हाल में प्रत्येक नोड कि अभी तक दौरा नहीं किया गया था में प्रवेश करती है (रों डीएफएस के स्यूडोकोड।)। उस अर्थ में, प्रत्येक vertex एक चक्र की एक संभावित शुरुआत प्रदर्शित करता है। इसके अतिरिक्त, चूंकि डीएफएस एक बार प्रत्येक किनारे पर जाता है, प्रत्येक किनारे एक चक्र के शुरुआती बिंदु तक पहुंचता है। इस प्रकार, डीएफएस और बैक-एज जांच का उपयोग करके ग्राफ में सभी चक्रों का पता लगाना संभवतः संभव होना चाहिए। ध्यान दें, यदि प्रतिभागी नोड्स की विभिन्न संख्या वाले चक्र मौजूद हैं (जैसे त्रिकोण, आयताकार इत्यादि), प्रत्येक चक्र के acutal "आकार" को भेदभाव करने के लिए अतिरिक्त कार्य किया जाना है।

Answer 1

प्रत्येक बढ़त केवल एक बार, तो यह सब चक्र मिलते हैं, तो एक ट्रेवर्सल एल्गोरिथ्म का दौरा। एक किनारे कई चक्रों का हिस्सा हो सकता है।

btw, एक बैक-धार क्या है?

इसके अलावा, शायद आप अलग तरीके से व्यक्त करना चाहिए/आपके सवाल का प्रारूप। पढ़ना बहुत मुश्किल है।

Answer 2

मैं पहले से ही इस अच्छी तरह से उत्तर दिया, तो यह जाँच की है:

Will a source-removal sort always return a maximal cycle?

जवाब के प्रासंगिक भाग:

अपने ग्राफ पर प्रदर्शन करना एक गहराई-प्रथम खोजें।

आप ट्रेवर्सल में, वापस किनारों, यानी पहचानने में रुचि रखते हैं, एक बढ़त जो एक पूर्वज को वापस अंक ( में डीएफएस पेड़ है, जो पहली बार के लिए जाकर नोड्स के किनारों से प्रेरित है) देखे गए नोड का। उदाहरण के लिए, यदि डीएफएस स्टैक में [ए-> बी-> सी-> डी] नोड्स हैं और जब आप डी का पता लगाते हैं तो आपको किनारे डी-> बी मिलते हैं, यह पीछे एज है। प्रत्येक पिछला किनारा एक चक्र को परिभाषित करता है।

इससे भी महत्वपूर्ण बात, चक्र प्रेरित बैक-किनारों से ग्राफ के चक्र का एक बुनियादी सेट कर रहे हैं। " चक्रों का एक मूल सेट": आप यूनियनिंग और मूल सेट के XORING चक्रों द्वारा ग्राफ के सभी चक्र ग्राफ़ का निर्माण कर सकते हैं। उदाहरण के लिए, चक्र [ए 1-> ए 2-> ए 3-> ए 1] और [ए 2-> बी 1-> बी 2-> बी 3-> ए 2] पर विचार करें। आप उन्हें चक्र में जोड़ सकते हैं: [ए 1-> ए 2-> बी 1-> बी 2-> बी 3-> ए 2-> ए 3-> ए 1]।

Answer 3

शायद यह आपकी मदद कर सकता है, मुझे this साइट मिली जहां निर्देशित ग्राफ के लिए रंगीन डीएफएस वर्णित है। तो आप यहाँ मौजूद php में dfs अनुवाद को सही करने पर विचार कर सकते हैं।

जो मैंने जोड़ा है वह सभी चक्रों को खोजने के लिए वन और एक अन्य भाग बनाने का एक हिस्सा है। तो कृपया ध्यान दें कि मेरे कोड के इन दो हिस्सों को निश्चित रूप से सही के रूप में सुरक्षित रखना सुरक्षित नहीं है।

ग्राफ सिद्धांत पर ज्ञान के साथ एक निश्चित रूप से परीक्षण करने में सक्षम हो सकता है। डीएफएस भाग में कोई टिप्पणी नहीं है क्योंकि यह पहले से ही संदर्भ साइट में वर्णित है। मेरा सुझाव है कि आप एक से अधिक पेड़ के साथ एक उदाहरण लें और बेहतर समझने के लिए एक पेपर में जंगल (4 रंगों की आवश्यकता है) खींचें।

इस कोड है:

<?php 

    //define the graph 
    $g = Array(
    1 => Array(1,2,3,4,5), 
    2 => Array(1,2,3,4,5), 
    3 => Array(1,2,3,4,5), 
    4 => Array(1,2,3,4,5), 
    5 => Array(1,2,3,4,5) 
    ); 

    //add needed attributes on the graph 
    $G = Array(); 
    foreach($g as $name => $children) 
    { 
     $child = Array(); 
     foreach($children as $child_name)//attaching a v letter is not needed, just a preference 
      $child['v'.$child_name] = null; 

     $G['v'.$name] = 
     Array('child'=>$child, 
      'color'=>'WHITE',//is used in dfs to make visit 
      'discover_time'=>null,//is used in dfs to classify edges 
      'finish_time'=>null,//is used in dfs to classify edges     
      'father'=>null,//is used to walk backward to the start of a cycle 
      'back_edge'=>null//can be omited, this information can be found with in_array(info, child_array) 
     ); 
    } 


new test($G); 
class test 
{ 
    private $G = Array();//graph 
    private $C = Array();//cycles 
    private $F = Array();//forest 
    private $L = Array();//loops 
    private $time_counter = 0; 

    public function __construct($G) 
    { 
     $this->G = $G; 

     foreach($this->G as $node_name => $foo) 
     { 
      if($this->G[$node_name]['color'] === 'WHITE') 
       $this->DFS_Visit($node_name); 
     } 

     $tree =array(); 
     foreach($this->G as $node_name => $data) 
     { 
      if($data['father'] === null)//new tree found 
      { 
       $this->F[] = $tree;//at first an empty array is inserted 
       $tree = Array(); 
       $tree[$node_name] = $data; 
      } 
      else 
       $tree[$node_name] = $data; 
     } 
     array_shift($this->F);//remove the empty array 
     $this->F[] = $tree;//add the last tree 

     $this->find_all_elementary_cycles(); 

     file_put_contents('dump.log', count($this->L)." Loops found: \n", FILE_APPEND); 
     file_put_contents('dump.log', print_r($this->L,true)."\n", FILE_APPEND); 

     file_put_contents('dump.log', count($this->C)." Cycles found: \n", FILE_APPEND); 
     file_put_contents('dump.log', print_r($this->C,true)."\n", FILE_APPEND); 

     file_put_contents('dump.log', count($this->F)." trees found in the Forest: \n", FILE_APPEND); 
     file_put_contents('dump.log', print_r($this->F,true)."\n", FILE_APPEND); 
    } 

    public function find_all_elementary_cycles() 
    { 
     /*** For each tree of the forest ***/ 
     foreach($this->F as $tree) 
     { 
      /*** Foreach node in the tree ***/ 
      foreach($tree as $node_name => $node) 
      { 
       /*** If this tree node connects to some child with backedge 
       (we hope to avoid some loops with this if) ***/ 
       if ($node['back_edge'] === true) 
        /*** Then for every child ***/ 
        foreach ($node['child'] as $child_name => $edge_classification) 
         if($edge_classification === 'BACK_EDGE') 
          $this->back_edge_exploit($node_name, $child_name, $tree);    
      } 
     } 
    } 

    private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree) 
    { 
     /*** The input of this function is a back edge, a back edge is defined as follows 
     -a sender node: which stands lower in the tree and a reciever node which of course stands higher 
     ***/ 

     /*** We want to get rid of loops, so check for a loop ***/ 
     if($back_edge_sender == $back_edge_receiver) 
      return $this->L[] = $back_edge_sender;//we need to return cause no there is no cycle in a loop 

     /*** For this backedge sender node the backedge reciever might send a direct edge to the sender ***/ 
     if(isset($this->G[$back_edge_receiver]['child'][$back_edge_sender]) > 0) 
      /*** This edge that the reciever sends could be a tree edge, this will happen 
      -in the case that: the backedge reciever is a father, but it can be a forward edge 
      -in this case: for the forward edge to exist the backedge reciever does not have to be 
      -a father onlly: it can also be an ancestore. Whatever of both cases, we have a cycle 
      ***/ 
      if($this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'TREE_EDGE' or 
       $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'FORWARD_EDGE') 
        $this->C[md5(serialize(Array($back_edge_receiver,$back_edge_sender)))] 
        = Array($back_edge_receiver,$back_edge_sender); 


     /*** Until now we have covered, loops, cycles of the kind father->child which occur from one tree edge 
     - and one: back edge combination, and also we have covered cycles of the kind ancestore->descendant 
     -which: occur from the combination of one forward edge and one backedge (of course might happen that 
     -a father: can send to the child both forward and tree edge, all these are covered already). 
     -what are left: are the cycles of the combination of more than one tree edges and one backedge ***/ 
     $cycle = Array(); 
     attach_node://loops must be handled before this, otherwise goto will loop continously 
     $cycle[] = $back_edge_sender; //enter the backedge sender 
     $back_edge_sender = $tree[$back_edge_sender]['father']; //backedge sender becomes his father 
     if($back_edge_sender !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet 
      goto attach_node;//the loop again 

     $cycle[] = $back_edge_receiver; 
     $cycle = array_reverse($cycle); 
     $this->C[md5(serialize($cycle))] = $cycle; 
    } 


    private function DFS_Visit($node_name) 
    { 
     $this->G[$node_name]['color'] = 'GRAY'; 
     $this->G[$node_name]['discover_time'] = $this->time_counter++; 

     foreach($this->G[$node_name]['child'] as $child_name => $foo) 
     {    
       if($this->G[$child_name]['color'] === 'BLACK') {#child black 

        if($this->G[$node_name]['discover_time'] < 
        $this->G[$child_name]['discover_time']){#time of father smaller 
         $this->G[$node_name]['child'][$child_name] = 'FORWARD_EDGE'; 
        } 
        else{#time of child smaller 
         $this->G[$node_name]['child'][$child_name] = 'CROSS_EDGE'; 
        } 
       } 
       elseif($this->G[$child_name]['color'] === 'WHITE'){#child white 
        $this->G[$node_name]['child'][$child_name] = 'TREE_EDGE'; 
        $this->G[$child_name]['father'] = $node_name;#father in the tree 
        $this->DFS_Visit($child_name); 
       }#child discovered but not explored (and father discovered) 
       elseif($this->G[$child_name]['color'] === 'GRAY'){#child gray 
        $this->G[$node_name]['child'][$child_name] = 'BACK_EDGE'; 
        $this->G[$node_name]['back_edge'] = true; 
       } 
     }//for 
     $this->G[$node_name]['color'] = 'BLACK';//fully explored 
     $this->G[$node_name]['finish_time'] = $this->time_counter++; 
    } 

} 

?> 

और यह उत्पादन होता है:

5 Loops found: Array (
    [0] => v1 
    [1] => v2 
    [2] => v3 
    [3] => v4 
    [4] => v5) 

16 Cycles found: Array (
    [336adbca89b3389a6f9640047d07f24a] => Array 
     (
      [0] => v1 
      [1] => v2 
     ) 

    [d68df8cdbc98d846a591937e9dd9cd70] => Array 
     (
      [0] => v1 
      [1] => v3 
     ) 

    [cad6b68c862d3a00a35670db31b76b67] => Array 
     (
      [0] => v1 
      [1] => v2 
      [2] => v3 
     ) 

    [1478f02ce1faa31e122a61a88af498e4] => Array 
     (
      [0] => v2 
      [1] => v3 
     ) 

    [0fba8cccc8dceda9fe84c3c93c20d057] => Array 
     (
      [0] => v1 
      [1] => v4 
     ) 

    [c995c93b92f8fe8003ea77617760a0c9] => Array 
     (
      [0] => v1 
      [1] => v2 
      [2] => v3 
      [3] => v4 
     ) 

    [8eae017bc12f0990ab42196af0a1f6a8] => Array 
     (
      [0] => v2 
      [1] => v4 
     ) 

    [57c0cc445b506ba6d51dc3c2f06fd926] => Array 
     (
      [0] => v2 
      [1] => v3 
      [2] => v4 
     ) 

    [18cef1bbe850dca5d2d7b6bfea795a23] => Array 
     (
      [0] => v3 
      [1] => v4 
     ) 

    [e0bd0c51bfa4df20e4ad922f57f6fe0d] => Array 
     (
      [0] => v1 
      [1] => v5 
     ) 

    [6a8b7681b160e28dd86f3f8316bfa16e] => Array 
     (
      [0] => v1 
      [1] => v2 
      [2] => v3 
      [3] => v4 
      [4] => v5 
     ) 

    [85e95d3e4dc97e066ec89752946ccf0c] => Array 
     (
      [0] => v2 
      [1] => v5 
     ) 

    [633c7cf8df43df75a24c104d9de09ece] => Array 
     (
      [0] => v2 
      [1] => v3 
      [2] => v4 
      [3] => v5 
     ) 

    [769f8ebc0695f46b5cc3cd444be2938a] => Array 
     (
      [0] => v3 
      [1] => v5 
     ) 

    [87028339e63fd6c2687dc5488ba0818c] => Array 
     (
      [0] => v3 
      [1] => v4 
      [2] => v5 
     ) 

    [c2b28cdcef48362ceb0d8fb36a142254] => Array 
     (
      [0] => v4 
      [1] => v5 
     ) 

) 

1 trees found in the Forest: Array (
    [0] => Array 
     (
      [v1] => Array 
       (
        [child] => Array 
         (
          [v1] => BACK_EDGE 
          [v2] => TREE_EDGE 
          [v3] => FORWARD_EDGE 
          [v4] => FORWARD_EDGE 
          [v5] => FORWARD_EDGE 
         ) 

        [color] => BLACK 
        [discover_time] => 0 
        [finish_time] => 9 
        [father] => 
        [back_edge] => 1 
       ) 

      [v2] => Array 
       (
        [child] => Array 
         (
          [v1] => BACK_EDGE 
          [v2] => BACK_EDGE 
          [v3] => TREE_EDGE 
          [v4] => FORWARD_EDGE 
          [v5] => FORWARD_EDGE 
         ) 

        [color] => BLACK 
        [discover_time] => 1 
        [finish_time] => 8 
        [father] => v1 
        [back_edge] => 1 
       ) 

      [v3] => Array 
       (
        [child] => Array 
         (
          [v1] => BACK_EDGE 
          [v2] => BACK_EDGE 
          [v3] => BACK_EDGE 
          [v4] => TREE_EDGE 
          [v5] => FORWARD_EDGE 
         ) 

        [color] => BLACK 
        [discover_time] => 2 
        [finish_time] => 7 
        [father] => v2 
        [back_edge] => 1 
       ) 

      [v4] => Array 
       (
        [child] => Array 
         (
          [v1] => BACK_EDGE 
          [v2] => BACK_EDGE 
          [v3] => BACK_EDGE 
          [v4] => BACK_EDGE 
          [v5] => TREE_EDGE 
         ) 

        [color] => BLACK 
        [discover_time] => 3 
        [finish_time] => 6 
        [father] => v3 
        [back_edge] => 1 
       ) 

      [v5] => Array 
       (
        [child] => Array 
         (
          [v1] => BACK_EDGE 
          [v2] => BACK_EDGE 
          [v3] => BACK_EDGE 
          [v4] => BACK_EDGE 
          [v5] => BACK_EDGE 
         ) 

        [color] => BLACK 
        [discover_time] => 4 
        [finish_time] => 5 
        [father] => v4 
        [back_edge] => 1 
       ) 

     ) 

) 

संपादित करें 1: back_edge_exploit विधि इस संस्करण द्वारा erplaced जा सकता है:

![private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree) 
{ 
    /*** The input of this function is a back edge, a back edge is defined as follows 
    -a sender node: which stands lower in the tree and a reciever node which of course stands higher 
    ***/ 

    /*** We want to get rid of loops, so check for a loop ***/ 
    if($back_edge_sender == $back_edge_receiver) 
     return $this->L\[\] = $back_edge_sender;//we need to return cause no there is no cycle in a loop 

    $cycle = Array();//There is always a cycle which is a combination of tree edges and on backedge 
    $edges_count = 0; //If the cycle has more than 2 nodes we need to check for forward edge 
    $backward_runner = $back_edge_sender;//this walks backward up to the start of cycle 

    attach_node://loops must be handled before this, otherwise goto will loop continously 
    $edges_count++; 
    $cycle\[\] = $backward_runner; //enter the backedge sender 
    $backward_runner = $tree\[$backward_runner\]\['father'\]; //backedge sender becomes his father 
    if($backward_runner !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet 
     goto attach_node;//the loop again 
    else 
     $cycle\[\] = $backward_runner; 

    if($edges_count>1 and $this->G\[$back_edge_receiver\]\['child'\]\[$back_edge_sender\] === 'FORWARD_EDGE') 
     $this->C\[\] = Array($back_edge_receiver,$back_edge_sender); 

    $this->C\[\] = array_reverse($cycle); //store the tree edge->back_edge cycle 
}][2] 

संपादित करें 2: मुझे यह कहना है कि मुझे पता चला है कि back_edge_exploit अपर्याप्त है, यह केवल पेड़ किनारों और एक बैक एज के साथ बनाए गए चक्र पाएगा।

**** संपादित करें 3: **** हालांकि यह समाधान अपूर्ण पाया गया है, लेकिन इसमें कुछ उपयोगी जानकारी है, यहां तक ​​कि अपर्याप्तता स्वयं स्वयं जानकारी का एक टुकड़ा है, इसलिए मुझे लगता है कि यह उपयोगी हो सकता है इसे रखें। लेकिन मुख्य कारण मैंने अपना जवाब संपादित किया है कि मुझे एक अन्य समाधान मिला है जिसे मैं नीचे पेश करने जा रहा हूं।

लेकिन इससे पहले कि एक अन्य नोटिस डीएफएस एप्रोच के बारे में किया जा सकता है, ऐसे चक्र हैं जो सभी क्रॉस, फॉरवर्ड, पेड़, बैक एज के किसी भी वैध संयोजन को चलकर हो सकते हैं। तो DFS जानकारी तुच्छ नहीं है पर निर्भर वास्तविक चक्र की खोज (अतिरिक्त कोड की आवश्यकता है), इस उदाहरण पर विचार करें:

जब तक नए समाधान यह 1970 के एक पुराने पत्र में वर्णित है का सवाल है , जेम्स सी। टियरनान (Check this link) द्वारा निर्देशित ग्राफ में सभी प्राथमिक चक्र खोजने के लिए एक कुशल एल्गोरिदम के रूप में। इसके अलावा गेटो See it here

प्राथमिक चक्र एल्गोरिदम (वह नाम) का मेरा कार्यान्वयन PHP में है और जितना संभव हो सके मूल के करीब है। मैंने इसे पहले से ही चेक कर लिया है और यह काम करता है। यह निर्देशित ग्राफ के बारे में है, यदि आप ग्राफ को घोषित करते हैं ताकि एक निर्देशित चक्र v1-> v2-> v3 और एक अन्य v2-> v3-> v1 हो तो दोनों चक्र पाए जाएंगे जो तर्कसंगत है क्योंकि यह निर्देशित पर काम करता है रेखांकन।

अप्रत्यक्ष ग्राफ के लिए लेखक अन्य एल्गोरिदम सुझाता है जो एल्गोरिदम को संशोधित करने से बेहतर समाधान करता है, हालांकि इसे ग्राफ परिभाषा को संशोधित करके और लंबाई 2 के चक्रों के लिए अतिरिक्त जांच जोड़कर किया जा सकता है जिसे अप्रत्यक्ष किनारों के रूप में माना जाता है । विशेष रूप से तीन नोड्स का एक अप्रत्यक्ष चक्र परिभाषा में दो बार परिभाषित किया जाएगा, एक बार प्रति अभिविन्यास, इस तरह: v1-> v2-> v3 और v3-> v2-> v1। फिर एल्गोरिदम इसे प्रतिबिंबित करने के बाद दो बार मिल जाएगा, फिर EC3_Circuit_Confirmation पर एक पंक्ति का एक संशोधन अतिरिक्त कटौती कर सकता है।

नोड्स क्रमशः परिभाषित किए गए हैं, कोई निरंतर first और आसन्नता सूची को शून्य या एक से पहले नोड गणना करने के लिए बदल सकता है।

यह Tiernan की चुनाव आयोग एल्गोरिथ्म के लिए php कोड है:

<?php 

    define(first,1); //Define how to start counting, from 0 or 1 
    //nodes are considered to be sequential 
    $G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1); 


    $N=key(array_slice($G, -1, 1, TRUE));//last key of g 
    $H=Array(Array()); 
    $P = Array(); 
    $P[first] = first; 
    $k = first; 
    $C = Array();//cycles 
    $L = Array();//loops 

########################## ALGORITHM START ############################# 

    #[Path Extension] 
    EC2_Path_Extension: 
    //scan adjacency list 
     foreach($G[$P[$k]] as $j => $adj_node) 
      //if there is an adjacent node bigger than P[1] and this nodes does not belong in P 
      if(($adj_node > $P[first]) and (in_array($adj_node, $P))===false and 
      (count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false) 
      { 
       $k++; 
       $P[$k] = $G[$P[$k-1]][$j]; 
       goto EC2_Path_Extension;  
      } 

    #[EC3 Circuit Confirmation] 
    EC3_Circuit_Confirmation: 
    if(!in_array($P[first], $G[$P[$k]])) 
     goto EC4_Vertex_Closure; 
    //otherwise 
    if (count($P)===1) 
     $L[] = current($P); 
    else 
     $C[] = implode($P); 


    #[EC4 Vertex Closure] 
    EC4_Vertex_Closure: 
    if($k===first) 
     goto EC5_Advance_Initial_Vertex; 

    $H[$P[$k]] = Array(); 
    $H[$P[$k-1]][] = $P[$k]; 
    unset($P[$k]); 
    $k--; 
    goto EC2_Path_Extension; 


    #[EC5 Advance Initial Vertex] 
    EC5_Advance_Initial_Vertex: 
    if($P[first] === $N) 
     goto EC6_Terminate; 

    $P[first]++; 
    $k=first; 
    //Reset H 
    $H=Array(Array()); 
    goto EC2_Path_Extension; 

    EC6_Terminate: 
########################### ALGORITHM END ################################## 

    echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n"; 
    echo count($C)." cycles found!\n".implode("\n",$C)."\n"; 

    /*** Original graph found in the paper ***/ 
    //$G[first] = Array(2); $G[] = Array(2,3,4); 
    //$G[] = Array(5); $G[] = Array(3); $G[] = Array(1); 


    ?> 

Answer 4

मेरे सुझाव प्रभावशाली तरीके से कनेक्ट घटकों के सेट मिल करने के लिए Tarjan एल्गोरिथ्म का उपयोग करना है, और Hierholzer एल्गोरिथ्म प्रभावशाली तरीके से कनेक्ट घटक के सभी चक्रों को खोजने के लिए । http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html