C++ の動作確認をしてみた（８１）

C++の練習を兼ねて, AtCoder Beginner Contest 002 の問題D (D – 派閥) を解いてみた.

■感想.
1. 解説上, 最大クリーク問題について触れられていたので, 最大クリーク問題として解いたら, どうなるか見てみた.
2. 新しい知識が一つ増えたので良かったと思う.

本家のサイトAtCoder Beginner Contest 002 解説をご覧下さい.

■C++版プログラム(問題D／AC版).

// 最大クリーク問題とみて解いてみる.
// 以下のライブラリを使ってみる(※一部改変).
// Maximum Clique using backtracking in C
// http://www.martinbroadhurst.com/maximum-clique-using-backtracking-in-c.html
#include <bits/stdc++.h>
using namespace std;
int a[21][21];

static void maximum_clique_recursive(int **adj, int order, 
        int *current_clique, int *current_clique_size, int *max_clique,
        int *max_clique_size, int level){
    int i, connected;
    if(level == order){
        /* Found a new max clique */
        memcpy(max_clique, current_clique, order * sizeof(int));
        *max_clique_size = *current_clique_size;
        return;
    }
    /* Find out if current vertex is connected to all vertices in current clique */
    connected = 1;
    for(i = 0; i < level && connected; i++){
        if(current_clique[i] && !adj[level][i]){
            connected = 0;
            break;
        }
    }

    if(connected){
        /* Add this vertex to the clique */
        current_clique[level] = 1;
        (*current_clique_size)++;
        maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique, 
                max_clique_size, level + 1);
        (*current_clique_size)--;
    }
    if(*current_clique_size + order - level > *max_clique_size){
        /* Still promising */
        current_clique[level] = 0;
        maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique, 
                max_clique_size, level + 1);
    }
}

int maximum_clique(int **adj, int order, int **max_clique){
    int max_clique_size = 0;
    int current_clique_size = 0;
    int *current_clique = (int *)malloc(order * sizeof(int));
    *max_clique = (int *)malloc(order * sizeof(int));
    if(current_clique == NULL || *max_clique == NULL){
        free(current_clique);
        free(max_clique);
        return 0;
    }
    maximum_clique_recursive(adj, order, current_clique, &current_clique_size, *max_clique, 
            &max_clique_size, 0);
    free(current_clique);
    return max_clique_size;
}

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    for(int i = 0; i < M; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        a[x][y]++;
        a[y][x]++;
    }
    
    // 2. 最大クリーク数を計算.
    int *adj[N];
    for(int i = 0; i < N; i++) adj[i] = a[i];
    int *max_clique = 0;
    int max_clique_size = maximum_clique(adj, N, &max_clique);
    
    // 3. 出力.
    printf("%d\n", max_clique_size);
    // for(int i = 0; i < N; i++) if(max_clique[i] == 1) printf("%u ", i);
    // putchar('\n');

    // 4. 後処理.
    free(max_clique);
    return 0;
    
}

// 最大クリーク問題とみて解いてみる.

// 以下のライブラリを使ってみる(※一部改変).

// Maximum Clique using backtracking in C

// http://www.martinbroadhurst.com/maximum-clique-using-backtracking-in-c.html

#include <bits/stdc++.h>

using namespace std;

int a[21][21];

static void maximum_clique_recursive(int **adj, int order,

int *current_clique, int *current_clique_size, int *max_clique,

int *max_clique_size, int level){

int i, connected;

if(level == order){

/* Found a new max clique */

memcpy(max_clique, current_clique, order * sizeof(int));

*max_clique_size = *current_clique_size;

return;

}

/* Find out if current vertex is connected to all vertices in current clique */

connected = 1;

for(i = 0; i < level && connected; i++){

if(current_clique[i] && !adj[level][i]){

connected = 0;

break;

}

if(connected){

/* Add this vertex to the clique */

current_clique[level] = 1;

(*current_clique_size)++;

maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique,

max_clique_size, level + 1);

(*current_clique_size)--;

}

if(*current_clique_size + order - level > *max_clique_size){

/* Still promising */

current_clique[level] = 0;

maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique,

max_clique_size, level + 1);

}

int maximum_clique(int **adj, int order, int **max_clique){

int max_clique_size = 0;

int current_clique_size = 0;

int *current_clique = (int *)malloc(order * sizeof(int));

*max_clique = (int *)malloc(order * sizeof(int));

if(current_clique == NULL || *max_clique == NULL){

free(current_clique);

free(max_clique);

return 0;

}

maximum_clique_recursive(adj, order, current_clique, &current_clique_size, *max_clique,

&max_clique_size, 0);

free(current_clique);

return max_clique_size;

}

int main(){

// 1. 入力情報取得.

int N, M;

scanf("%d %d", &N, &M);

for(int i = 0; i < M; i++){

int x, y;

scanf("%d %d", &x, &y);

x--, y--;

a[x][y]++;

a[y][x]++;

}

// 2. 最大クリーク数を計算.

int *adj[N];

for(int i = 0; i < N; i++) adj[i] = a[i];

int *max_clique = 0;

int max_clique_size = maximum_clique(adj, N, &max_clique);

// 3. 出力.

printf("%d\n", max_clique_size);

// for(int i = 0; i < N; i++) if(max_clique[i] == 1) printf("%u ", i);

// putchar('\n');

// 4. 後処理.

free(max_clique);

return 0;

}

[入力例]
5 3
1 2
2 3
1 3

[出力例(debug版)]
3
0 1 2 
※AtCoderテストケースより

[入力例]
7 9
1 2
1 3
2 3
4 5
4 6
4 7
5 6
5 7
6 7

[出力例(debug版)]
4
3 4 5 6 
※AtCoderテストケースより

[入力例]
10 21
1 2
1 3
2 3
6 5
8 6
6 7
8 9
5 7
6 7
7 9
1 3
3 8
9 6
6 7
7 8
10 2
10 3
6 10
7 10
8 10
9 10

[出力例(debug版)]
5
5 6 7 8 9 

[入力例]
7 18
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
3 4
3 5
3 6
3 7
4 5
4 6
5 6
5 7

[出力例(debug版)]
6
0 1 2 3 4 5

[入力例]

5 3

1 2

2 3

1 3

[出力例(debug版)]

0 1 2

※AtCoderテストケースより

[入力例]

7 9

1 2

1 3

2 3

4 5

4 6

4 7

5 6

5 7

6 7

[出力例(debug版)]

3 4 5 6

※AtCoderテストケースより

[入力例]

10 21

1 2

1 3

2 3

6 5

8 6

6 7

8 9

5 7

6 7

7 9

1 3

3 8

9 6

6 7

7 8

10 2

10 3

6 10

7 10

8 10

9 10

[出力例(debug版)]

5 6 7 8 9

[入力例]

7 18

1 2

1 3

1 4

1 5

1 6

1 7

2 3

2 4

2 5

2 6

3 4

3 5

3 6

3 7

4 5

4 6

5 6

5 7

[出力例(debug版)]

0 1 2 3 4 5

■参照サイト
AtCoder Beginner Contest 002
Maximum Clique using backtracking in C

C++の練習を兼ねて, AtCoder Beginner Contest 002 の 問題D (D – 派閥) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 002 の問題D (D – 派閥) を解いてみた.

コメントを残すコメントをキャンセル