前回、ほったらかしにしておいたやつを、ついに実装出来たので、メモしておきます。
クラスを自分で定義したの、はじめてかも?
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