无向图的最大团等于其补图的最大独立集
无向图的最大独立集等于其补图的最大团。
一、Maximum Clique HDU - 1530 ：
Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.
Input
Input contains multiple tests. For each test:
The first line has one integer n, the number of vertex. (1 < n <= 50)
The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number).
A test with n = 0 signals the end of input. This test should not be processed.
Output
One number for each test, the number of vertex in maximum clique.
Sample Input
5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0
Sample Output
4
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=55;
int a[maxn][maxn];
bool ha[maxn];
int now_num,max_num;
int n;
bool check(int x)
{
for (int i=1;i<x;i++)
{
if (ha[i]&&!a[x][i]) return false;
}
return true;
}
void dfs(int x)
{
if (x>n)
{
max_num=max(max_num,now_num);
return ;
}
if (check(x))
{
now_num++;
ha[x]=1;
dfs(x+1);
now_num--;
}
if (now_num+n-x>max_num)
{
ha[x]=0;
dfs(x+1);
}
}
int main()
{
while(scanf("%d",&n),n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
now_num=max_num=0;
memset(ha,0,sizeof(ha));
dfs(1);
printf("%d\n",max_num);
}
return 0;
}
dfs回溯法八秒卡过HDU，但是ZOJ华丽丽的T了（time limited enough）。
Bron-Kerbosch 算法 HDU 2s，但是ZOJ 280ms 轻松过掉
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=55;
int n;
int a[maxn][maxn];
int cnt[maxn];//cnt[i]为>=i的最大团点数
int group[maxn];//最大团的点
int vis[maxn];//记录点的位置
int max_num;//最大团的数目
bool dfs(int pos,int now_num)//num为已取的点数
{
for(int i=pos+1;i<=n;i++)
{
if(cnt[i]+now_num<=max_num)//剪枝，若取i但cnt[i]+已经取了的点数仍<ans
return false;
if(a[pos][i])//与当前团中元素比较，取Non-N(i)
{
int j=0;
for(j=0;j<now_num;j++)
if(!a[i][vis[j]])
break;
if(j==now_num) //若为空，则皆与i相邻，则此时将i加入到最大团中
{
vis[now_num]=i;
if(dfs(i,now_num+1))
return true;
}
}
}
if(now_num>max_num) //每添加一个点最多使最大团数+1,后面的搜索就没有意义了
{
max_num=now_num;//最大团中点的数目
for(int i=1;i<=now_num;i++)//最大团的元素
group[i]=vis[i-1];
return true;
}
return false;
}
void maxClique()
{
max_num=-1;
for(int i=n;i>=1;i--) //枚举所有点
{
vis[0]=i;
dfs(i,1);
cnt[i]=max_num;
}
}
int main(){
while(scanf("%d",&n),n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
maxClique();
printf("%d\n",max_num);//最大团的个数
}
return 0;
}
dfs加剪枝，HDU 1560ms，ZOJ 20ms
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn = 55;
int mp[maxn][maxn];
int best, n, num[maxn];
bool dfs(int *adj, int total, int cnt)
{
int t[maxn],k;
if(total==0)
{
if(cnt>best)
{
best=cnt;
return true; //剪枝4
}
return false;
}
for(int i=0;i<total;i++)
{
if(cnt+total-i<=best) return false; //剪枝1
if(cnt+num[adj[i]]<=best) return false; //剪枝3
k = 0;
for(int j=i+1;j<total;j++)
if(mp[adj[i]][adj[j]]) t[k++]=adj[j];
//扫描与u相连的顶点中与当前要选中的adj[i]相连的顶点adj[j]并存储到数组t[]中，数量为k
if(dfs(t,k,cnt+1)) return true;
}
return false;
}
int MaximumClique()
{
int adj[maxn],k;
best=0;
for(int i=n;i>=1;i--)
{
k=0;
for(int j=i+1;j<=n;j++)
if(mp[i][j]) adj[k++]=j;
//得到当前点i的所有相邻点存入adj
dfs(adj,k,1); //每次dfs相当于必选当前i点看是否能更新best
num[i]=best;
}
return best;
}
int main()
{
while(scanf("%d",&n),n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&mp[i][j]);
}
printf("%d\n",MaximumClique());
}
return 0;
}
二、Graph Coloring POJ - 1419
You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph and the only available colors are black and white. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes may be black.
Figure 1: An optimal graph with three black nodes
Input
The graph is given as a set of nodes denoted by numbers 1…n, n <= 100, and a set of undirected edges denoted by pairs of node numbers (n1, n2), n1 != n2. The input file contains m graphs. The number m is given on the first line. The first line of each graph contains n and k, the number of nodes and the number of edges, respectively. The following k lines contain the edges given by a pair of node numbers, which are separated by a space.
Output
The output should consists of 2m lines, two lines for each graph found in the input file. The first line of should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring. It is given by the list of black nodes, separated by a blank.
Sample Input
1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
Sample Output
3
1 4 5
求最大独立集，转换为求补图的最大团。
暴力一发 16ms
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=108;
int a[maxn][maxn];
bool ha[maxn];
int ans[maxn];
int now_num,max_num;
int n,m;
bool check(int x)
{
for (int i=1;i<x;i++)
{
if (ha[i]&&!a[x][i]) return false;
}
return true;
}
void dfs(int x)
{
if (x>n)
{
if(now_num>max_num)
{
max_num=now_num;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(ha[i])
ans[++cnt]=i;
}
return ;
}
return ;
}
if (check(x))
{
now_num++;
ha[x]=1;
dfs(x+1);
now_num--;
}
if (now_num+n-x>max_num)
{
ha[x]=0;
dfs(x+1);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int x,y;
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
a[i][j]^=1;
}
now_num=max_num=0;
memset(ha,0,sizeof(ha));
dfs(1);
printf("%d\n",max_num);
for(int i=1;i<=max_num;i++)
{
if(i!=1) putchar(' ');
printf("%d",ans[i]);
}
putchar('\n');
}
return 0;
}
还是16ms（这题是不是没数据啊。。。。）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=108;
int n,m;
int a[maxn][maxn];
int cnt[maxn];
int group[maxn];
int vis[maxn];
int max_num;
bool dfs(int pos,int now_num)
{
for(int i=pos+1;i<=n;i++)
{
if(cnt[i]+now_num<=max_num)
return false;
if(a[pos][i])
{
int j=0;
for(j=0;j<now_num;j++)
if(!a[i][vis[j]])
break;
if(j==now_num)
{
vis[now_num]=i;
if(dfs(i,now_num+1))
return true;
}
}
}
if(now_num>max_num)
{
max_num=now_num;
for(int i=1;i<=now_num;i++)
group[i]=vis[i-1];
return true;
}
return false;
}
void maxClique()
{
max_num=-1;
for(int i=n;i>=1;i--)
{
vis[0]=i;
dfs(i,1);
cnt[i]=max_num;
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
a[i][j]^=1;
}
maxClique();
printf("%d\n",max_num);
for(int i=1;i<=max_num;i++)
{
if(i!=1) putchar(' ');
printf("%d",group[i]);
}
putchar('\n');
}
return 0;
}
0ms 搞定：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn = 108;
int mp[maxn][maxn];
int best,num[maxn];
int group[maxn],vis[maxn];
int n,m;
bool dfs(int *adj, int total, int cnt)
{
int t[maxn],k;
if(total==0)
{
if(cnt>best)
{
for(int i=1;i<=cnt;i++)
group[i]=vis[i-1];
best=cnt;
return true;
}
return false;
}
for(int i=0;i<total;i++)
{
if(cnt+total-i<=best) return false;
if(cnt+num[adj[i]]<=best) return false;
k = 0,vis[cnt]=adj[i];
for(int j=i+1;j<total;j++)
if(mp[adj[i]][adj[j]]) t[k++]=adj[j];
if(dfs(t,k,cnt+1)) return true;
}
return false;
}
int MaximumClique()
{
int adj[maxn],k;
best=0;
for(int i=n;i>=1;i--)
{
k=0,vis[0]=i;
for(int j=i+1;j<=n;j++)
if(mp[i][j]) adj[k++]=j;
dfs(adj,k,1);
num[i]=best;
}
return best;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(mp,0,sizeof(mp));
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
mp[i][j]^=1;
}
int maxx=MaximumClique();
printf("%d\n",maxx);
for(int i=1;i<=maxx;i++)
{
if(i!=1) putchar(' ');
printf("%d",group[i]);
}
putchar('\n');
}
return 0;
}
三、All Friends POJ - 2989 ：
Sociologists are interested in the phenomenon of “friendship”. To study this property, they analyze various groups of people. For each two persons in such a group they determine whether they are friends (it is assumed that this relation is symmetric). The sociologists are mostly interested in the sets of friends. The set S of people is the set of friends if every two persons in S are friends. However, studying the sets of friends turns out to be quite complicated, since there are too many such sets. Therefore, they concentrate just on the maximal sets of friends. A set of friends S is maximal if every person that does not belong to S is not a friend with someone in S.
Your task is to determine the number of maximal sets of friends in each group. In case this number exceeds 1 000, you just need to report this – such a group is too complicated to study.
Input
The input consists of several instances, separated by single empty lines.
The first line of each instance consists of two integers 1 ≤ n ≤ 128 and m – number of persons in the group and number of friendship relations. Each of m following lines consists of two integers ai and bi (1 ≤ ai, bi ≤ n). This means that persons ai and bi (ai ≠ bi) are friends. Each such relationship is described at most once.
Output
The output for each instance consists of a single line containing the number of maximal sets of friends in the described group, or string “Too many maximal sets of friends.” in case this number is greater than 1 000.
Sample Input
5 4
1 2
3 4
2 3
4 5
Sample Output
4
没怎么看懂，以后看懂了再回来写题解，先贴一个转载了的题解。
//要用Bron–Kerbosch算法。找最大团，
//我们设了三个数组：all, some, none,
//分别表示的是已经选了的点，还没动的点，不要的点(避免重复，实际上就是判重)。
//算法的思想是将some中的点逐步加入all和none中，
//当我们将一个点v放入all中时，把和它有连接的点的点集
//交上当前的some点集，就是下一个的some点集，
//同样，none也是一样的，这样保证了团中的点互相连接
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=130;
int n,m,g[maxn][maxn];
int S,all[maxn][maxn],some[maxn][maxn],none[maxn][maxn];
//all为已取顶点集，some为未处理顶点集，none为不取的顶点集
//我们求最大团顶点数时只要some，要求记录路径时要all和some，
//这里求极大团数量，需要all、some、none
void dfs(int d, int an, int sn, int nn)
{
if(sn==0&&nn==0) ++S;//sn==0搜索到终点，只有nn==0时，才是一个极大团
if(S>1000) return ; // 极大团数量超过1000就不再统计
int u = some[d][1];//pivot vertex
for(int i=1;i<=sn;i++)
{
int v=some[d][i];
if(g[u][v]) continue;
int tsn=0,tnn=0;
for(int j=1;j<=an;j++) all[d+1][j]=all[d][j];
all[d+1][an+1]=v;
for(int j=1;j<=sn;j++)
if(g[v][some[d][j]]) some[d+1][++tsn]=some[d][j];
for(int j=1;j<=nn;j++)
if(g[v][none[d][j]]) none[d+1][++tnn]=none[d][j];
dfs(d+1,an+1,tsn,tnn);
//把v从some取出，放入none
some[d][i]=0,none[d][++nn]=v;
}
}
void work()
{
S = 0;
for(int i=1;i<=n;i++) some[0][i]=i;
dfs(0, 0, n, 0);
if(S>1000) printf("Too many maximal sets of friends.\n");
else printf("%d\n", S);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(g,0,sizeof(g));
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=1;
}
work();
}
return 0;
}
京公网安备 11010502036488号