AOJ2222 Alien's Counting

AOJ Volume22

問題リンク Alien's Counting

  • 概要

指がN本あるエイリアンがいる。人間が指を折って数を数えるようにエイリアンも指を折って数を数える。エイリアンにはM個の指を折るルールがある。ルールは2つの整数A、Bで与えられ、Aを折ると常にBも同時に折れることを表す。Bを折ると常にAも折れるということを表しているわけではない。エイリアンはいったいいくつまで数を数えることができるか答えよ。
1 <= N <= 1000
0 <= M <= 1000

  • 解法

メモ化DPで解きました。
指の番号を頂点、ルール(A, B)に対して有向辺A->Bを張ったグラフを考えます。このグラフを強連結成分分解すると、1つの指として考えてよい部分が縮約され、DAGになります。
ここで、DAGの始点から組み合わせを計算していきます。
DAGの頂点kについて以下のようなDP表を用意します。(説明が分かりづらいかもしれません><)
dp[k][0]: 頂点kが葉となるような部分グラフにおいて、指kを折らない場合の組み合わせ数
dp[k][1]: 頂点kが葉となるような部分グラフにおいて、指kを折る場合の組み合わせ数
この表の埋め方を説明します。
頂点kがDAGの始点の頂点だった場合、部分グラフは自分自身なので、自明にdp[k][0] = dp[k][1] = 1です。
そうでない場合
dp[k][0]は指を折らない場合なので、DAGの始点から頂点kに至るまで、どの指も折ってはなりません。折ってしまうと、指折りのルールの連鎖で指kも折れてしまうからです。なので、kの全ての親の頂点v(祖先は含まず親のみ)について、dp[v][0]を掛け合わせたものがdp[k][0]となります。
dp[k][1]は部分グラフにおいてどこか1か所でも指を折ればいいので、結局
dp[k][1] *= (dp[v][0] + dp[v][1])
になります。
この表を作成したら、DAGの葉となっている頂点vについて、
res *= (dp[v][0] + dp[v][1])
としてやれば答えになります。
自分のソースプログラムでは、葉の頂点から考えているのでメモ化になっています。

  • ソース
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

//Alien's Counting
public class AOJ2222 {

	Set<Integer>[] e, rev, in, out;
	int N, M;
	long MOD = 1000000007;
	
	int[] scc;
	boolean[] u;
	List<Integer> list;
	
	long[][] dp;
	
	void dfs(int k){
		u[k] = true;
		for(int v:e[k])if(!u[v])dfs(v);
		list.add(k);
	}
	void rdfs(int k, int id){
		u[k] = true;
		scc[k] = id;
		for(int v:rev[k])if(!u[v])rdfs(v, id);
	}

	long get(int k){
		if(dp[k][0]!=-1)return (dp[k][0]+dp[k][1])%MOD;
		dp[k][0] = dp[k][1] = 1;
		for(int v:out[k]){
			dp[k][1]*=get(v);
			dp[k][1]%=MOD;
			dp[k][0]*=dp[v][0];
			dp[k][0]%=MOD;
		}
		return (dp[k][0]+dp[k][1])%MOD;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		e = new Set[N];
		rev = new Set[N];
		for(int i=0;i<N;i++){
			e[i] = new HashSet<Integer>();
			rev[i] = new HashSet<Integer>();
		}
		while(M--!=0){
			int s = sc.nextInt()-1, t = sc.nextInt()-1;
			e[s].add(t);
			rev[t].add(s);
		}
		list = new ArrayList<Integer>();
		u = new boolean[N];
		for(int i=0;i<N;i++)if(!u[i])dfs(i);
		Arrays.fill(u, false);
		int ID = 0;
		scc = new int[N];
		for(int i=list.size()-1;i>=0;i--){
			int j = list.get(i);
			if(u[j])continue;
			rdfs(j, ID);
			ID++;
		}
		in = new Set[ID];
		out = new Set[ID];
		for(int i=0;i<ID;i++){
			in[i] = new HashSet<Integer>();
			out[i] = new HashSet<Integer>();
		}
		for(int i=0;i<N;i++){
			for(int v:rev[i]){
				if(scc[i]==scc[v])continue;
				out[scc[i]].add(scc[v]);
				in[scc[v]].add(scc[i]);
			}
		}
		dp = new long[ID][2];
		for(long[]d:dp)Arrays.fill(d, -1);
		long res = 1;
		for(int i=0;i<ID;i++)if(in[i].isEmpty()){
			res*=get(i);
			res%=MOD;
		}
		System.out.println(res);
	}

	public static void main(String[] args) {
		new AOJ2222().run();
	}
}