刷题记（无向图的极大团与最大团）

CONTENT: 无向图的极大团与最大团的Bron–Kerbosch算法
DETAIL: Bron–Kerbosch算法个人的一点理解 PROBLEMS:
ZOJ 1492
CF 1105E

BB

最大团 / 最大独立集网上资料蛮少的 QAQ
因此这篇文会稍微细致的说一下蒟蒻理解的Bron–Kerbosch算法

Introduction

有诸多不严谨的地方，见谅QAQ，参考

概念相关
极大团：无向图的最大完全子图
最大团：所有极大团中顶点数最多的（在图中选k个点，使得这k个点都相连，并且k最大）最大独立集：在图中选k个点，使得这k个点都不相连，并且k最大
最大独立集 = 图的补图的最大团

Bron–Kerbosch算法求极大团

BronKerbosch(all, some, none):
   if some ∪ none = ∅:
       return all
   for each vertex v in some:
       BronKerbosch(all U {v}, some ∩ Next(v), none ∩ Next(v))
       some = some - {v}
       none = none ∪ {v}

其中all为目前已确定为极大团的顶点集合，some为未处理的顶点集合，none为已处理过的顶点集合，Next(v)表示与点v相连的顶点集合
假设some集合不在每次操作后移除点v，那么搜到点v时，此时假定该极大团必定包含点v，那么接下来的搜索对象就应该为some ∩ Next(v)，一直搜索到some为空集时，此时all集合便是点点相连的，即all集合组成一个极大团
但是，这样会造成效率低下与重复计数的问题，为此，引入集合none，并在每次搜索回溯时将点v从集合some移入集合none
那么在集合some为空时，若集合none不为空，说明有之前搜索过的点，若此时该团为极大团，那么其应当在之前就已经被计入，因此此时不做处理，否则这是一个新的极大团

优化的(With pivoting)Bron–Kerbosch算法求极大团

BronKerbosch(all, some, none):
   if some ∪ none = ∅:
       return all
   u = a pivot vertex in some ∪ none
   for each vertex v in some - Next(u):
       BronKerbosch(all U {v}, some ∩ Next(v), none ∩ Next(v))
       some = some - {v}
       none = none ∪ {v}

可以在some ∪ none中选择一个pivot点u，下次只需要在some - Next(u)中搜索即可，因为
当点u在some中时，假定最后all集合包含了点u，那么这部分工作只需要交给枚举到点u时再去搜索Next(u)即可，而不需要这时候搜索，要是all集合没有包含点u，那么Next(u)的部分则是交给后续遍历其他点获得
当点u在none中时，最后all集合必定没有包含点u，其他同上

最后，有个带剪枝的搜索算法求最大团，用一点点注释写在板子里面了

Maximum Clique - ZOJ - 1492

Link
https://cn.vjudge.net/problem/ZOJ-1492
Solution1：求极大团模板 (560 ms)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 128 + 15;

int some[N][N], all[N][N], none[N][N];
int G[N][N];

int dfs(int d, int an, int sn, int nn, int sum) {
    if(!sn && !nn) {
        return sum;
    }

    int ans = 0;
    int u = some[d][0];
    for(int i = 0; i < sn; i++) {
        int v = some[d][i];
        if(G[u][v]) {
            continue;
        }

        for(int j = 0; j < an; j++) {
            all[d + 1][j] = all[d][j];
        }
        all[d + 1][an] = v;

        int tsn = 0, tnn = 0;
        for(int j = 0; j < sn; j++) {
            if(!G[v][some[d][j]]) {
                continue;
            }
            some[d + 1][tsn++] = some[d][j];
        }
        for(int j = 0; j < nn; j++) {
            if(!G[v][none[d][j]]) {
                continue;
            }
            none[d + 1][tnn++] = none[d][j];
        }

        ans = max(ans, dfs(d + 1, an + 1, tsn, tnn, sum + 1));
        some[d][i] = 0;
        none[d][nn++] = v;
    }
    return ans;
}

inline int solve(int n) {
    for(int i = 1; i <= n; i++) {
        some[0][i - 1] = i;
    }
    return dfs(0, 0, n, 0, 0);
}

int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d", &G[i][j]);
            }
        }

        printf("%d\n", solve(n));
    }
}

Solution2：求最大团模板 (20 ms)

#include <bits/stdc++.h>
const int N = 50 + 15;

int G[N][N];
int num[N];  //维护V[i] ... v[n]的最大团

bool dfs(int adj[], int an, int cnt, int& ans) {
    if(an == 0) {
        if(cnt > ans) {
            ans = cnt;
            return true;
        }
        return false;
    }

    int tmp[N];
    for(int i = 0; i < an; i++) {
        //剪枝
        if(cnt + an - i <= ans || cnt + num[adj[i]] <= ans) {
            return false;
        }

        int k = 0;
        for(int j = i + 1; j < an; j++) {
            if(!G[adj[i]][adj[j]]) {
                continue;
            }
            tmp[k++] = adj[j];
        }

        if(dfs(tmp, k, cnt + 1, ans)) {
            return true;
        }
    }
    return false;
}

int solve(int n) {
    int adj[N];
    int ans = 0;
    //从后往前枚举，利用num[i]
    for(int i = n; i >= 1; i--) {
        int k = 0;
        for(int j = i + 1; j <= n; j++) {
            if(!G[i][j]) {
                continue;
            }
            adj[k++] = j;
        }
        dfs(adj, k, 1, ans);
        num[i] = ans;
    }
    return ans;
}

int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d", &G[i][j]);
            }
        }

        printf("%d\n", solve(n));
    }
}

Helping Hiasat - CodeForces - 1105E

Link
https://cn.vjudge.net/problem/CodeForces-1105E
Description
翻译来自洛谷
你在某社交网站上面注册了一个新账号，这个账号有n(n <= 10^5)次记录。要么就是你更改过一次ID，要么就是一个ID为s(|s| <= 40)的朋友访问过你的空间。
你有m(m <= 40)个朋友。每一个朋友都会访问你的空间至少一次。如果这一个朋友每一次访问你的空间的时候，你的ID和它的ID一样，那么他就会高兴。求你最多能让多少人高兴。
Sample Input

3
1
motarack
mike
1
light

3
1
alice
bob
tanyaromanova

Sample Output

2
1

Solution：最大独立集
实际上就是求最大独立集顶点个数
正解不会QAQ

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
const int M = 40 + 5;

struct Input {
    int op;
    string s;
};
Input in[N];
int val[N];
unordered_map<string, int> mp;
int mptot;

int G[M][M];
int num[N];

bool dfs(int adj[], int an, int cnt, int& ans) {
    if(an == 0) {
        if(cnt > ans) {
            ans = cnt;
            return true;
        }
        return false;
    }

    int tmp[M];
    for(int i = 0; i < an; i++) {
        if(cnt + an - i <= ans || cnt + num[adj[i]] <= ans) {
            return false;
        }

        int k = 0;
        for(int j = i + 1; j < an; j++) {
            if(!G[adj[i]][adj[j]]) {
                continue;
            }
            tmp[k++] = adj[j];
        }

        if(dfs(tmp, k, cnt + 1, ans)) {
            return true;
        }
    }
    return false;
}

int solve(int n) {
    int adj[M];
    int ans = 0;
    for(int i = n; i >= 1; i--) {
        int k = 0;
        for(int j = i + 1; j <= n; j++) {
            if(!G[i][j]) {
                continue;
            }
            adj[k++] = j;
        }
        dfs(adj, k, 1, ans);
        num[i] = ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    while(cin >> n >> m) {
        memset(G, 0, sizeof(G));
        mptot = 0;

        for(int i = 0; i < n; i++) {
            cin >> in[i].op;
            if(in[i].op == 2) {
                cin >> in[i].s;

                if(mp.count(in[i].s) == 0) {
                    mp.insert(make_pair(in[i].s, ++mptot));
                }
                val[i] = mp[in[i].s];
            }
        }

        for(int i = 0, l = -1, r = -1, tag = 0; i < n; i++) {
            if(in[i].op == 2 && tag == 0) {
                l = i;
                tag = 1;
            }
            if(tag && (in[i].op == 1 || i == n - 1)) {
                tag = 0;
                r = i + (in[i].op != 1);

                sort(val + l, val + r);
                r = unique(val + l, val + r) - val;

                for(int j = l; j < r; j++) {
                    for(int k = j + 1; k < r; k++) {
                        int u = val[j], v = val[k];
                        G[u][v] = G[v][u] = 1;
                    }
                }
            }
        }

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= m; j++) {
                if(i == j) {
                    continue;
                }
                G[i][j] ^= 1;
            }
        }

        cout << solve(m) << endl;
    }
}