Location>code7788 >text

"Graph Theory" Bron-kerbosch Algorithm

Popularity:966 ℃/2024-07-23 22:12:46
Note: It is recommended to read the algorithmic process section of this blog first to make it easier to read the code comments
int to[N][N], mnt; //to[i][j] is used to determine if i to j are connected, mnt is the number of points in the largest group.
int had[N][N], may[N][N], vis[N][N]; //had, may, vis represent the points in the group currently being searched, the points that may join the group currently being searched, and the points that have already been searched (corresponding to the algorithmic process of the set R, P, X, respectively).
The first dimension i of //had,may,vis denotes the i-th level of the search, and the second dimension j denotes the number of corresponding points.

//d denotes the current search in the layer, R,P,X denote the number of points in the layer of search for had,may,vis, respectively.
void Bron_Kerbosch(int d, int R, int P, int X){
if(!P and !X){ mnt = max(mnt, R); return;} //find a very large cluster
for(int i=1; i<=P; i++){
int u = may[d][i]; // take points from P

for(int j=1; j<=R; j++){
had[d+1][j] = had[d][j];
} had[d+1][R+1] = u; //i.e., the operation R' = R + {u}

int newP = 0, newX = 0;
for(int j=1; j<=P; j++) // P' = P ∩ Q(u)
if(to[u][may[d][j]])) may[d+1][++newP] = may[d][j];

for(int j=1; j<=X; j++) // X' = X ∩ Q(u)
if(to[u][vis[d][j]])) vis[d+1][++newX] = vis[d][j];

Bron_Kerbosch(d+1, R+1, newP, newX); //recursive search

may[d][i] = 0, vis[d][++X] = u; // remove point u from P and add it to X
}
}

At this point, it's already A-OK for that night's extra game.T2.7 Lose Me Up.

AC Code
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;

const int N = 50;

int n, m, x, hnt;
int to[N][N];
int had[N][N], may[N][N], vis[N][N];

void Bron_Kerbosch(int d, int R, int P, int X){
	if(!P and !X){ hnt = max(hnt, R); return; }
	for(int i=1; i<=P; i++){
		int u = may[d][i];

		for(int j=1; j<=R; j++){
			had[d+1][j] = had[d][j];
		} had[d+1][R+1] = u;

		int newP = 0, newX = 0;
		for(int j=1; j<=P; j++)
			if(to[u][may[d][j]]) may[d+1][++newP] = may[d][j];

		for(int j=1; j<=X; j++)
			if(to[u][vis[d][j]]) vis[d+1][++newX] = vis[d][j];

		Bron_Kerbosch(d+1, R+1, newP, newX);

		may[d][i] = 0, vis[d][++X] = u;
	}
}

signed main(){
	// freopen("", "r", stdin); freopen("", "w", stdout);

	scanf("%d%d%d", &n, &m, &x);
	for(int i=1; i<=m; i++){
		int a, b; scanf("%d%d", &a, &b);
		to[a][b] = to[b][a] = 1;
	}

	int num = 0;
	for(int i=1; i<=n; i++)
		may[1][++num] = i;

	Bron_Kerbosch(1, 0, num, 0);

	double ans = x * 1.0 / hnt;
	ans *= ans;
	ans *= ((hnt - 1) * hnt / 2);
	printf("%.6lf", ans);

	return 0;
}

However, this algorithm can also be used by setting the pivot vertex\(v\) Optimization. The main optimization principles are described inoi-wiki

Optimized Code (Pure Enjoyment Edition):

int to[N][N], hnt;
int had[N][N], may[N][N], vis[N][N];

void Bron_kerbosch(int d, int R, int P, int X){
    if(!P and !X) { hnt = max(hnt, R); return;}
    int u = may[d][1];

    for(int i=1; i<=P; i++){
        int v = may[d][i];
        if(to[u][v]) continue;

        for(int j=1; j<=R; j++){
            had[d+1][j] = had[d][j];
        } had[d+1][R+1] = v;

        int newP = 0, newX = 0;
        for(int j=1; j<=P; j++)
            if(to[v][may[d][j]]) may[d+1][++newP] = may[d][j];
        for(int j=1; j<=X; j++)
            if(to[v][vis[d][j]]) vis[d+1][++newX] = vis[d][j];
        
        Bron_kerbosch(d+1, R+1, newP, newX);

        may[d][i] = 0, vis[d][++X] = v;

    }
}