POJ 2793 - Cactus

http://poj.org/problem?id=2793

概要

どの辺も高々1つのシンプルな閉路にしか含まれていないような連結無向グラフを cactus と呼ぶ。 あるグラフが cactus なとき、cactus な全域部分グラフをいくつも考えることができる。 あるグラフの cactusness を、そのグラフの全域部分グラフのうち cactus なものの数と定義したとき、 与えられた \(n\) 頂点のグラフの cactusness を答える。 ただし、与えられたグラフがそもそも cactus でないときの cactusness は 0 と定義する。

入力は \(m\) 個のパス情報からなり、\(i\) 番目のパス情報には \(k_i\) 個の頂点が並んでおり、 この順に頂点を結ぶ無向辺が存在することを表している。

制約

解法

辺にマークをつけながら DFS して、 閉路を検出したらそこに含まれている辺のすべてに閉路に含まれているマークをつけ、 そのときに既に辺に閉路マークがついていたら2つの閉路に含まれていることになるため cactus でないことがわかる。

与えられた無向グラフが cactus であるとき、cactusness は閉路の長さから計算できる。 閉路に含まれていない辺を取り除くと連結でなくなってしまうので、これを取り除くことはできない。 閉路に含まれている辺に関しては、1つの閉路にしか含まれていないため、その閉路からは高々1つの辺しか取り除くことができない。 よって、長さ \(l\) の閉路からは、どれか1つの辺を取り除くか、どの辺も取り除かない \(l+1\) 通りの cactus な部分グラフが得られる。 したがって、各閉路の長さを \(l_i\) とすると、\(l_i + 1\) の積が cactusness となる

BigInteger のために Java で。

  1 import java.util.*;
  2 import java.io.*;
  3 import java.math.*;
  4 
  5 public class Main {
  6   static class Edge {
  7     int from, to;
  8     boolean[] visited, looped;
  9     Edge(int from, int to, boolean[] visited, boolean[] looped) {
 10       this.from = from;
 11       this.to = to;
 12       this.visited = visited;
 13       this.looped = looped;
 14     }
 15   }
 16 
 17   static class NotCactusError extends Exception {
 18   }
 19 
 20   public static void main(String[] args) {
 21     new Main().run();
 22   }
 23 
 24   List<List<Edge>> g;
 25   BigInteger ans;
 26   LinkedList<Edge> history;
 27   List<Boolean> visited;
 28 
 29   void run() {
 30     Scanner cin = new Scanner(System.in);
 31     int N = cin.nextInt();
 32     int M = cin.nextInt();
 33     g = new ArrayList<List<Edge>>();
 34     visited = new ArrayList<Boolean>();
 35     for (int i = 0; i < N; i++) {
 36       g.add(new ArrayList<Edge>());
 37       visited.add(false);
 38     }
 39     for (int i = 0; i < M; i++) {
 40       int K = cin.nextInt();
 41       int prev = cin.nextInt();
 42       --prev;
 43       for (int j = 1; j < K; j++) {
 44         int u = cin.nextInt();
 45         --u;
 46         boolean[] b = new boolean[1];
 47         boolean[] l = new boolean[1];
 48         b[0] = l[0] = false;
 49         g.get(prev).add(new Edge(prev, u, b, l));
 50         g.get(u).add(new Edge(u, prev, b, l));
 51         prev = u;
 52       }
 53     }
 54     try {
 55       ans = BigInteger.ONE;
 56       history = new LinkedList<Edge>();
 57       dfs(0, 0);
 58       if (checkConnected()) {
 59         System.out.println(ans);
 60       } else {
 61         System.out.println("0");
 62       }
 63     } catch (NotCactusError e) {
 64       System.out.println("0");
 65     }
 66   }
 67 
 68   boolean checkConnected() {
 69     for (boolean b : visited) {
 70       if (!b) {
 71         return false;
 72       }
 73     }
 74     return true;
 75   }
 76 
 77   void dfs(int n, int steps) throws NotCactusError {
 78     if (visited.get(n)) {
 79       Iterator<Edge> it = history.iterator();
 80       int len = 0;
 81       while (it.hasNext()) {
 82         Edge e = it.next();
 83         if (e.looped[0]) {
 84           throw new NotCactusError();
 85         }
 86         e.looped[0] = true;
 87         ++len;
 88         if (e.from == n) {
 89           break;
 90         }
 91       }
 92       ans = ans.multiply(BigInteger.valueOf(len+1));
 93     } else {
 94       visited.set(n, true);
 95       for (Edge e : g.get(n)) {
 96         if (!e.visited[0]) {
 97           e.visited[0] = true;
 98           history.addFirst(e);
 99           dfs(e.to, steps+1);
100           history.pollFirst();
101         }
102       }
103     }
104   }
105 }
poj/2793.java