Viz 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ší.

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);
}