[Algorithm] 🍞ハイキング

1.問題の解釈

友達をあげるときは、友達である子供たちの間でペアリングをします.
入力
Case(c)
人数(n)、友人数(m)
友達をリストする
しゅつりょく
ペアリングメソッドの合計

2.アイデア

💡 友達ペアを格納する2 D配列
💡 ペアリングされているかどうかを決定する1次元アレイ.
💡 ペアリングの組合せの問題:再帰関数の使用

3.解答

1)友人の身分を受け入れて保存する
boolean friends[][] = new boolean[n][n];
friends[x][y] = true;
2)アレイを作成してペアを組むかどうかを決定する
boolean taken[] = new boolean[n];
3)再帰関数によるDFSの実現
taken[pairOne] = taken[pairTwo] = true;
dfs(taken);
taken[pairOne] = taken[pairTwo] = false;

4.コード

import java.util.*;

public class Picnic {
	static int c,n,m;
	static boolean friends[][] = new boolean[10][10];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		c = sc.nextInt();
		int result[] = new int[c];
		
		for(int i=0; i<c; i++) {
			n = sc.nextInt();
			m = sc.nextInt();
			
			boolean taken[] = new boolean[n];
			
			for(int j=0; j<m; j++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				
				friends[x][y] = true;
				friends[y][x] = true;
			}
			result[i] = count(taken);
		}
		
		for(int i=0; i<c; i++)
			System.out.println(result[i]);
	
		sc.close();
	}
	
	public static int count(boolean taken[]) {
		int pairOne = -1;
		
		for(int i=0; i<n; i++) {
			if(!taken[i]) {
				pairOne = i;
				break;
			}
		}
		
		if(pairOne == -1)
			return 1;
		
		int ret = 0;
		
		for(int pairTwo=pairOne+1; pairTwo<n; pairTwo++) {
			if(!taken[pairTwo] && friends[pairOne][pairTwo] == true) {
				taken[pairTwo] = true;
				taken[pairOne] = true;
				ret += count(taken);
				taken[pairTwo] = false;
				taken[pairOne] = false;
			}
		}
		return ret;
	}

}

5.結果

間違っている