==== Úloha 3 Molecule Complexes ====

Viz [[https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=moleculecomplexes|Zadání]].

V úloze máme najít v daném acyklickém grafu všechny takové cykly délky 5, které neobsahují žádnou příčku.

Myšlenka řešení:

**1.**  Uzly si libovolně uspořádáme (například použijeme vstupní pořadí) a pak z každého uzlu X spustíme BFS do hloubky 2. Při prohledávání neuvažujeme uzly s nižším pořadím, než je pořadí uzlu X. Pokud existuje nějaký hledaný cyklus, který 
prochází X a uzlem Y s nižším pořadím, než je pořadí X, musel být tento cyklus objeven již dříve, a to nejpozději když se spouštělo BFS  z uzlu Y.

**2.**  Vyjdeme z uzlu X a projdeme všechny vhodné (viz 1.) dvojice (Z, Y) jeho sousedů. Pro každého souseda sZ vrcholu Z a pro každého souseda sY vrcholu Y zkontrolujeme, zda sZ a sY jsou spojeny hranou. Pokud ano a pokud neexistují hrany 
{X, sZ}, {X, sY}, {X, S}, {Y, sZ}, {Z, sY}, objevili jsme cyklus, který si poznamenáme.  
 
**3.** Při hledání cyklu musíme používat hrany, které případně cyklus tvoří, a kontrolovat neexistenci hran, které by představovaly příčku v cyklu. Musíme proto rychle umět rozhodnout, zda daná dvojice vrcholů představuje hranu nebo ne.
Pro malé grafy stačí matice sousednosti, pro velké grafy se vyplatí mít množinu hran uloženu v hashovací tabulce. Oba přístupy zajišťují konstantní dobu ověřování existence hrany.


**4.** Uzlů je N, každý má O(N^2) dvojic sousedů, to je celkem O(N^3) kontrolovaných dvojic sousedů. Pro každou dvojici (Z, Y) musíme zkontrolovat všechny sousedy Z vůči všem sousedům Y, což má opět složitost  O(N^2), celkem tedy máme složitost  O(N^5). Horní hranice složitosti však bude dosaženo jen na velmi hustých grafech. Pokud shora omezíme stupně uzlů číslem P, dotaneme pomocí stejné úvahy složitost O(N * P^4), což je mnohem příznivější. 

<code C>
package alg;

import java.io.*;
import java.util.*;

public class Z05 {
  
// graph
static int N, M;
static int [][] g; // array of arrays of neighbors -- so called list representation
static int [] dg;  // node degrees

// set of all edges, each edge is in format <node1>*2^24 + <node2>
static long ff = 256*256*256L;
static HashSet<Long> hs;

// encode the edge for the hash set
static long eno(int n1, int n2) {
  if (n1 < n2) return n1*ff+n2;
  return n2*ff+n1;
}

static void searchFrom(int n1) {
  int jn2x = 0,  n2, n3, n4, n5;
  while ((jn2x < dg[n1]) && (g[n1][jn2x] < n1)) jn2x++;
  for(int jn2 = jn2x; jn2 < dg[n1] - 1; jn2++) {
    n2 = g[n1][jn2];
    if (n2 < n1) continue;
    for(int jn5 = jn2+1; jn5 < dg[n1]; jn5++) {
      n5 = g[n1][jn5];
      if (n5 < n1) continue;
      if (hs.contains(eno(n2, n5))) continue;
      for(int jn3 = 0; jn3 < dg[n2]; jn3++) {
        n3 = g[n2][jn3];
        if (n3 < n1) continue;
        if (hs.contains(eno(n1,n3)) || hs.contains(eno(n5,n3))) continue;
        for(int jn4 = 0; jn4 < dg[n5]; jn4++) {
          n4 = g[n5][jn4];
          if (n4 < n1) continue;
          if (!hs.contains(eno(n4,n3)) || hs.contains(eno(n1,n4)) || hs.contains(eno(n2,n4))) continue;
          // now it is there:
          printResult(n1, n2, n5, n3, n4);
        } // for n4
      } // for n3
    } // for n5
  } // for n2
}

// ***************************************************************************
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                            M A I N
// ...........................................................................
// ***************************************************************************

public static void main(String[] args) {

  readInput();
  
  // for easier processing keep the list of neighbors of any node sorted 
  for(int i = 0; i < N; i++)
    Arrays.sort(g[i], 0, dg[i]);
  
  for(int i = 0; i <= N-5; i++)
    searchFrom(i);
  
}

// ***************************************************************************
//                            I / O
// ***************************************************************************

static void  readInput() { try {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
  StringTokenizer st = new StringTokenizer(br.readLine());
  M = Integer.valueOf(st.nextToken());
  N = Integer.valueOf(st.nextToken());

  g = new int[N][2];
  dg = new int[N];
  
  hs = new HashSet<Long>();
  
  int n1, n2;
  for(int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    n1 = Integer.valueOf(st.nextToken());
    n2 = Integer.valueOf(st.nextToken());
    if (dg[n1] == g[n1].length) g[n1] = Arrays.copyOf(g[n1], 2*dg[n1]);
    if (dg[n2] == g[n2].length) g[n2] = Arrays.copyOf(g[n2], 2*dg[n2]);
    g[n1][dg[n1]++] = n2;
    g[n2][dg[n2]++] = n1;
    if (N < maxeeN) ee[n1][n2] = ee[n2][n1] = true;
    else hs.add(eno(n1,n2));
  } 
 }
  catch (IOException eee) 
    {System.out.printf("Santa Maria Madre de Dios! Excepcion, Excepciooon!!\n"); return ;}
}

// The output has to be sorted  

static void printResult(int n1, int a, int b, int c, int d) { 
  int low1, low2, high1, high2, lowest, mid1, mid2, highest;

  sols++;
  //if(2 > 1) return;
  if (a < b) { low1 = a; high1 = b; }
  else { low1 = b;  high1 = a; }
  if (c < d) {low2 = c;  high2 = d; }
  else { low2 = d; high2 = c;}
  if (low1 < low2) { lowest = low1;  mid1 = low2;}
  else {lowest = low2; mid1 = low1; }
  if (high1 > high2) { highest = high1; mid2 = high2; }
  else {highest = high2;  mid2 = high1; }
  if (mid1 < mid2)
        System.out.printf("%d %d %d %d %d\n", n1, lowest, mid1, mid2, highest);
  else   System.out.printf("%d %d %d %d %d\n", n1, lowest, mid2, mid1, highest);
}
       
</code>