プログラミングを上達させたい

情報学専攻の大学院→放送局でCMの営業など@大阪→舞台俳優&IT営業@東京

Javaで隣接リストを作るため、新しいクラスを定義するなど(CodeFestivalチーム早解きリレーのF問題)

前回、ほったらかしにしておいたやつを、ついに実装出来たので、メモしておきます。
クラスを自分で定義したの、はじめてかも?
Javaの基礎をろくに学ばずにいたため、こういうことが起こるのですね。まぁよい。


今回の問題はCodeFestival本選のチーム早解きリレーの問題Fです。
概要を書くと、
頂点数n、辺の数n、の連結グラフが与えられる(自己ループ、多重辺なし)。これはループをちょうど1つだけ含む。与えられるグラフのループの長さはいくらか。
条件:3 <= n <= 100000
形式:
n
x1 y1
x2 y2
....
xn yn
(nは頂点数(=辺の数)であり、頂点番号x1とy1が繋がっていて...xnとynが繋がっています。)

という問題です。

さて、これはチーム早解きリレー内で、僕が実装するかも?となったものの、結局Javaで隣接リストをどうやって作るのか分からず、パスした問題です(C++では簡単らしいです)。
しかし、チームにいた強い人にどうやって解くかは説明してもらったので、そのうちやろうと思っていました。
色々試しながらやった結果、ついに隣接リストの作り方が分かったので、自分へのメモという意味も含めて書いておきます。

まず、上の問題に対するコード(確かめてみたらACになりました)は以下のようなものです。

import java.util.*;
 
//エラーとかその辺は気にせず、あくまで上手く使ってくれる前提で作りました
//基本的に、普通のLinkedListの一部の機能が使えるだけ。ただ、Intが前提となっている。
class oneNodeList{
  LinkedList<Integer> list = new LinkedList<Integer>();
 
  public void push(int a){
    list.add(a);
  }
  public int poll(){
    int a = list.poll();
    return a;
  }
  public int peek(){
    int a = list.peek();
    return a;
  }

  //空ならtrueを返す
  public boolean isEmpty(){
    return list.isEmpty();
  } 
}
 
 
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
 
    int n = sc.nextInt();
 
    oneNodeList[] rinsetsuList = new oneNodeList[n];
 
    for(int i = 0; i < n; i++){
      rinsetsuList[i] = new oneNodeList();
    }
 
    for(int i = 0; i < n; i++){
      int haji1 = sc.nextInt() - 1;
      int haji2 = sc.nextInt() - 1;
      rinsetsuList[haji1].push(haji2);
      rinsetsuList[haji2].push(haji1);
    }
 
    int[] lenFromZero = new int[n];
 
    LinkedList<Integer> numstack = new LinkedList<Integer>();
    LinkedList<Integer> lenstack = new LinkedList<Integer>();
 
    lenFromZero[0] = 0;
    for(int i = 1; i < n; i++){
      lenFromZero[i] = -1;
    }
    numstack.push(0);
    lenstack.push(0);
 
    int answer = 0;
 
    while(n > 0){
      int nowFrom = numstack.poll();
      int nowLen = lenstack.poll();
 
      if(!rinsetsuList[nowFrom].isEmpty()){
        numstack.push(nowFrom);
        lenstack.push(nowLen);
 
        int nowTo = rinsetsuList[nowFrom].poll();
 
        if(lenFromZero[nowTo] < 0){
          lenFromZero[nowTo] = nowLen + 1;
          numstack.push(nowTo);
          lenstack.push(nowLen + 1);
        }else{
          //ループは必ず長さが3以上であることを利用して、さっきまでいた隣のノードに
          //帰らないようにチェック!
          if(nowLen + 1 - lenFromZero[nowTo] <= 2){
            continue;
          }else{
            answer = nowLen + 1 - lenFromZero[nowTo];
            break;
          }
        }
      }
    }
 
    System.out.println(answer);
  }
}

さて、説明を。
n <= 100000なので、グラフの辺を隣接行列(参考ページ(Wikipedia))で記憶しようとすると、とんでもないサイズになってしまいます。おおまかに言うとnの2乗に比例するサイズになってしまいます。
辺の数もnなので、隣接行列のほとんどの要素が0となってしまい、もったいないですね。
そこで、隣接リスト(参考ページ(Wikipedia))で記憶すると、nに比例するサイズで済みます。

ただ、それを可能にするためには、キューやスタック的な、長さを最初に決めない、可変長(というのでしょうか?)なものの配列を持つ必要があります。しかしJavaでは、普段の整数の配列と同じノリで

LinkedList<Integer>[] list = new LinkedList<Integer>()[];

と書いてもダメなのです。そこで、自分で(ほぼLinkedListやーんみたいな)クラスを作って、それの配列と書くようにする作戦に移りました。
それが"oneNodeList"というクラス(型?)です。


注意ですが、

    oneNodeList[] rinsetsuList = new oneNodeList[n];
 
    for(int i = 0; i < n; i++){
      rinsetsuList[i] = new oneNodeList();
    }

この部分を書くというのが分からず、少しつまずきました。
少し面倒ですよね。
新しく定義したclassだから?毎回new oneNodeListとして新しいインスタンスを作らないといけません。面倒。

しかし上のような書き方だと、なんかこう、冗長な感じがしますよね・・・。pushとかpollとか、もともとLinkedListにあるものをもう一度書くのは、何か上手いことできそうです。
多分、implements?とかそういう、オーバーライド?とかなんかそういう機能を使うと、省いたりできるんだと思います。
でも今回は面倒なので、しませんでした。だって面倒なんだもの。
(12/1追記:できました!この記事の一番下に、extendsを使って書いたものを付け足します。)

クラスを作る練習はもう少しやってみようということで、上のコードでスタックを2つ使うのを1つにする、というコードは書いてみました。
次のコードでは、新しく"node"という型を作り、node型のスタック1つで上と同じ動作をします。node型は、ノード番号と、0番目のノードからの距離の2つの整数を保持する型です。

import java.util.*;
 
 
//エラーとかその辺は気にせず、あくまで上手く使ってくれる前提で作りました
class oneNodeList{
  LinkedList<Integer> list = new LinkedList<Integer>();
 
  public void push(int a){
    list.add(a);
  }
  public int poll(){
    int a = list.poll();
    return a;
  }
  public int peek(){
    int a = list.peek();
    return a;
  }
  //空ならtrueを返す
  public boolean isEmpty(){
    return list.isEmpty();
  }
}
 
class node{
  int nodeIndex;
  int length;
}
 
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
 
    int n = sc.nextInt();
 
    oneNodeList[] rinsetsuList = new oneNodeList[n];
 
    for(int i = 0; i < n; i++){
      rinsetsuList[i] = new oneNodeList();
    }
 
    for(int i = 0; i < n; i++){
      int haji1 = sc.nextInt() - 1;
      int haji2 = sc.nextInt() - 1;
      rinsetsuList[haji1].push(haji2);
      rinsetsuList[haji2].push(haji1);
    }
 
    int[] lenFromZero = new int[n];
    lenFromZero[0] = 0;
    for(int i = 1; i < n; i++){
      lenFromZero[i] = -1;
    }
 
    LinkedList<node> stack = new LinkedList<node>();
    node startnode = new node();
    startnode.nodeIndex = 0;
    startnode.length = 0;
 
    stack.push(startnode);
 
    int answer = 0;
 
    while(n > 0){
      node nowNode = new node();
      nowNode = stack.poll();
 
      int nowFrom = nowNode.nodeIndex;
      int nowLen = nowNode.length;
 
      if(!rinsetsuList[nowFrom].isEmpty()){
        stack.push(nowNode);
 
        node newNode = new node();
 
        newNode.nodeIndex = rinsetsuList[nowFrom].poll();
        newNode.length = nowLen + 1;
 
        if(lenFromZero[newNode.nodeIndex] < 0){
          lenFromZero[newNode.nodeIndex] = newNode.length;
          stack.push(newNode);
        }else{
          if(newNode.length - lenFromZero[newNode.nodeIndex] <= 2){
            continue;
          }else{
            answer = newNode.length - lenFromZero[newNode.nodeIndex];
            break;
          }
        }
      }
    }
 
    System.out.println(answer);
  }
}

というわけで、今回はこれくらいです。
でも、なんか1つの大きな進歩のような気がします。新しい型が作れるようになった!

クラスについては、こちらの記事でも触れています。ご参考までに。

Javaで自分の作ったクラスに順序を入れる方法(Comparator編)(CodeFestivalあさぷろMiddle B問題) - プログラミングを上達させたい


12/1追記分
extendsを使うと、簡単に書くことができました。
上のoneNodeListというクラスの定義を、以下のように書き換えればOKでした。簡単!extendsはすごいぞ!

class oneNodeList extends LinkedList<Integer>{
}

これで、LinkedListと全く同じクラスとなります。これ、すんごく便利ですね。いえいいえーい!