C,C++の課題でわからないことがありました。

Question

http://abc002.contest.atcoder.jp/tasks/abc002_4
このサイトの問題のD問題でわからないものがありました。
http://www.slideshare.net/chokudai/abc002
↑がこの問題の解説なんですが、「全てのパターンを列挙して、その中で派閥を作れる中で一番大きい派閥の人数を出力する」とありました。これがいまいちよくわからなくて、全てのパターンを列挙したあとの処理がわかりません。他人のコードを見たりしましたが説明文がなくてよくわかりませんでした。下のコードが正解のコードみたいなんですけど、このコードの内容を詳しく解説していただけると幸いです。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int maxFaction(int N, int G[12][12], int f[12], int a)
{
int ret = 0;
int tmp = 0;
int i;

if (a == N) {
	for (i = 0; i < N; i++) {
		if (f[i] == 1) ret++;
	}
	return ret;
}

if (f[a] == 0) {
	for (i = 0; i < N; i++) {
		if (a == i) continue;
		if (f[i] == 1 && G[a][i] != 1) break;
	}
	if (i == N) {
		f[a] = 1;
		ret = maxFaction(N, G, f, a + 1);
		f[a] = 0;
	}
	tmp = maxFaction(N, G, f, a + 1);
	ret = (ret < tmp ? tmp : ret);
}

return ret;

}

int main()
{
int N, M;
int x, y;
int G[12][12] = { 0 };
int f[12];
int i;

cin >> N >> M;
for (i = 0; i < M; i++) {
	cin >> x >> y;
	--x, --y;
	G[x][y] = G[y][x] = 1;
}

memset(f, 0, sizeof(f));
printf("%d\n", maxFaction(N, G, f, 0));

return 0;

}

Answer 1

※完全な解説にはなっていないと思いますが、自分が試して分かったところまでを
書きます。

上記のコードよりも
http://www.slideshare.net/chokudai/abc002
P18 おたっくすさんの回答C++
の方がシンプルだったので、こちらを元に解説します。
こちらの回答も最大クリープ問題を再帰を使って解いています。

動作確認時のコードは以下になります。
(実際に動かす場合は矩形選択などで行頭の行数を削除ください)

1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 #include <map>
5 #include <set>
6 #include <algorithm>
7 #include <string>
8 #include <cstdlib>
9 #include <stack>
10 #include <queue>
11 #include <cmath>
12 using namespace std;
13
14 int N, M, f[12][12] = { 0 }, ans = 0;
15
16 void dfs(vector<int> v, int k = 0) {
17 //--------確認コードここから--------//
18 printf("v=[");
19 for (int i = 0; i < v.size(); i++) {
20 printf("%d", v[i]);
21 if (i != v.size() - 1) {
22 printf(", ");
23 }
24 }
25 printf("]");
26
27 printf(" k = %d\n", k);
28 //--------確認コードここまで--------//
29
30 if (k == N) {
31 for (int i = 0; i < v.size(); i++) {
32 for (int j = i + 1; j < v.size(); j++) {
33 if (f[v[i]][v[j]] == 0) {
34 //--------確認コードここから--------//
35 printf(" 知り合いでない関係がある\n");
36 //--------確認コードここまで--------//
37 return;
38 }
39 }
40 }
41 //--------確認コードここから--------//
42 printf(" ★全員知り合い (int)v.size() = %d\n", (int)v.size());
43 //--------確認コードここまで--------//
44 ans = max(ans, (int)v.size());
45 }
46 else {
47 dfs(v, k + 1);
48 v.push_back(k);
49 dfs(v, k + 1);
50 v.pop_back();
51 }
52 }
53
54 int main() {
55 cin >> N >> M;
56 for (int i = 0; i < M; i++) {
57 int x, y;
58 cin >> x >> y;
59 x--; y--;
60 f[x][y] = f[y][x] = 1;
61 }
62 vector<int> v;
63 dfs(v);
64 cout << ans << endl;
65 }

関数がどのように再帰で呼ばれているのかが
よく分からなかったので、dfs()の冒頭に、呼ばれた時点の
v, k を表示するようにしました。(17～28行目)

また、dfs()が呼ばれて、kがNと等しい場合にvで指定する人たちが
知り合いなのかを確認するため、確認結果を表示するようにしました。
(34～36, 41～43行目)

入力は以下を使用しました。
[input.txt]
5 3
1 2
2 3
3 4

入力データが、56～61行目で隣接行列(f[][])に格納されます。

実行すると、

v=[] k = 0
v=[] k = 1
v=[] k = 2
v=[] k = 3
v=[] k = 4
v=[] k = 5
  ★全員知り合い (int)v.size() = 0
v=[4] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3] k = 4
v=[3] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3, 4] k = 5
  知り合いでない関係がある
v=[2] k = 3
v=[2] k = 4
v=[2] k = 5
  ★全員知り合い (int)v.size() = 1
v=[2, 4] k = 5
  知り合いでない関係がある
v=[2, 3] k = 4
v=[2, 3] k = 5
  ★全員知り合い (int)v.size() = 2
v=[2, 3, 4] k = 5
  知り合いでない関係がある
v=[1] k = 2
v=[1] k = 3
v=[1] k = 4
v=[1] k = 5
  ★全員知り合い (int)v.size() = 1
v=[1, 4] k = 5
  知り合いでない関係がある
v=[1, 3] k = 4
v=[1, 3] k = 5
  知り合いでない関係がある
v=[1, 3, 4] k = 5
  知り合いでない関係がある
v=[1, 2] k = 3
v=[1, 2] k = 4
v=[1, 2] k = 5
  ★全員知り合い (int)v.size() = 2
v=[1, 2, 4] k = 5
  知り合いでない関係がある
v=[1, 2, 3] k = 4
v=[1, 2, 3] k = 5
  知り合いでない関係がある
v=[1, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0] k = 1
v=[0] k = 2
v=[0] k = 3
v=[0] k = 4
v=[0] k = 5
  ★全員知り合い (int)v.size() = 1
v=[0, 4] k = 5
  知り合いでない関係がある
v=[0, 3] k = 4
v=[0, 3] k = 5
  知り合いでない関係がある
v=[0, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 2] k = 3
v=[0, 2] k = 4
v=[0, 2] k = 5
  知り合いでない関係がある
v=[0, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 2, 3] k = 4
v=[0, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1] k = 2
v=[0, 1] k = 3
v=[0, 1] k = 4
v=[0, 1] k = 5
  ★全員知り合い (int)v.size() = 2
v=[0, 1, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 3] k = 4
v=[0, 1, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2] k = 3
v=[0, 1, 2] k = 4
v=[0, 1, 2] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3] k = 4
v=[0, 1, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3, 4] k = 5
  知り合いでない関係がある
2

と出ます。

k = 5時の出力を抜粋すると、

v=[] k = 5
  ★全員知り合い (int)v.size() = 0
v=[4] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3] k = 5
  ★全員知り合い (int)v.size() = 1
v=[3, 4] k = 5
  知り合いでない関係がある
v=[2] k = 5
  ★全員知り合い (int)v.size() = 1
v=[2, 4] k = 5
  知り合いでない関係がある
v=[2, 3] k = 5
  ★全員知り合い (int)v.size() = 2
v=[2, 3, 4] k = 5
  知り合いでない関係がある
v=[1] k = 5
  ★全員知り合い (int)v.size() = 1
v=[1, 4] k = 5
  知り合いでない関係がある
v=[1, 3] k = 5
  知り合いでない関係がある
v=[1, 3, 4] k = 5
  知り合いでない関係がある
v=[1, 2] k = 5
  ★全員知り合い (int)v.size() = 2
v=[1, 2, 4] k = 5
  知り合いでない関係がある
v=[1, 2, 3] k = 5
  知り合いでない関係がある
v=[1, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0] k = 5
  ★全員知り合い (int)v.size() = 1
v=[0, 4] k = 5
  知り合いでない関係がある
v=[0, 3] k = 5
  知り合いでない関係がある
v=[0, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 2] k = 5
  知り合いでない関係がある
v=[0, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 2, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1] k = 5
  ★全員知り合い (int)v.size() = 2
v=[0, 1, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 3, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 4] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3] k = 5
  知り合いでない関係がある
v=[0, 1, 2, 3, 4] k = 5
  知り合いでない関係がある

となります。
ここでvの値に注目すると、0,1,2,3,4の全ての組み合わせパターンが
現れています。
k = 5の時、それぞれの組み合わせパターンに対して
vの人たちが互いに知り合いかを、確認しています。(31～40行目)

また全員が知り合いの場合、その時点で調べているグループの人数(v.size())が
ansよりも大きければ、ansを更新します。(44行目)
★がついているところが全員知り合いの時ですが、
その時のグループ人数は0,1,2なので、最大値2が最終回答となります。

Answer 2

関数の再帰呼び出しについて調べると良いと思いますよ