图论 —— 弦图 —— MCS 算法
【概述】
MCS 算法是最大势算法(Maximum Cardinality Search),其常用于弦图的判定、求弦图的最大团、最小着色、最大独立集、最小团覆盖等。
一个无向图的弦图当且仅当其有一个完美消除序列,MCS 算法能够在 O(n+m) 内求出一个完美消除序列的反序。
每次执行 MCS 算法按从 n 到 1 的顺序依次给点标号,标号为 i 的点出现在完美消除序列的第 i 个,设 label[i] 为第 i 个点与多少个已标号点相邻,每次选择 label[i] 最大的未标号点进行标号,从而求一个完美消除序列的反序。
【算法核心】
vector<int> V[N];
void MCS() {
for(int i=1; i<=n; i++)
V[0].push_back(i);
int maxx=0;
int now=0;
for(int i=1; i<=n; i++) { //从前往后
bool flag=false;
while(!flag) {
for(int j=V[maxx].size()-1; j>=0; j--) { //从后往前
if(vis[V[maxx][j]])
V[maxx].pop_back();
else {
flag=true;
now=V[maxx][j];
break;
}
}
if(!flag)
maxx--;
}
vis[now]=true;
//逆序存放
order[n-i+1]=now;
id[now]=n-i+1;
for(int j=head[now]; j!=-1; j=edge[j].next) {
int to=edge[j].to;
if(!vis[to]) {
label[to]++;
V[label[to]].push_back(to);
maxx=max(maxx,label[to]);
}
}
}
}
【模版】
struct Edge {
int to,next;
Edge() {}
Edge(int to,int next):to(to),next(next) {}
};
struct MCS{
Edge edge[N<<1];
int head[N],tot;
int n,m;
bool vis[N];
int id[N];//编号
int label[N];//与多少标号点相邻
int order[N];//完美消除序列
vector<int> V[N];
void init(int n,int m) {
this->n=n;
this->m=m;
for(int i=1; i<=n; i++)
V[i].clear();
memset(head,-1,sizeof(head));
memset(order,0,sizeof(order));
memset(label,0,sizeof(label));
memset(vis,0,sizeof(vis));
memset(id,0,sizeof(id));
tot=0;
}
void addEdge(int x,int y) {
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot++;
}
void mcs() {
for(int i=1; i<=n; i++)
V[0].push_back(i);
int maxx=0;
int now=0;
for(int i=1; i<=n; i++) { //从前往后
bool flag=false;
while(!flag) {
for(int j=V[maxx].size()-1; j>=0; j--) { //从后往前
if(vis[V[maxx][j]])
V[maxx].pop_back();
else {
flag=true;
now=V[maxx][j];
break;
}
}
if(!flag)
maxx--;
}
vis[now]=true;
//逆序存放
order[n-i+1]=now;
id[now]=n-i+1;
for(int j=head[now]; j!=-1; j=edge[j].next) {
int to=edge[j].to;
if(!vis[to]) {
label[to]++;
V[label[to]].push_back(to);
maxx=max(maxx,label[to]);
}
}
}
}
int bucket[N];//桶
int judge() { //判断是否是弦图
memset(vis,0,sizeof(vis));
memset(bucket,0,sizeof(bucket));
for(int i=n; i>0; i--) {
int cnt=0;
int ret=1;
for(int j=head[order[i]]; j!=-1; j=edge[j].next)
if(id[edge[j].to]>i)
vis[bucket[++cnt]=edge[j].to]=1;
for(int j=head[bucket[1]]; j!=-1; j=edge[j].next) {
int to=edge[j].to;
if(to!=bucket[1]&&vis[to]) {
if(vis[to]) {
ret++;
vis[to]++;
}
}
}
for(int j=1; j<=cnt; j++)
vis[bucket[j]]=0;
if(cnt&&ret!=cnt)
return false;
}
return true;
}
int getMaximumClique() { //计算最大团、最小着色
int res=0;
for(int i=1; i<=n; i++)
res=max(res,label[i]+1);
return res;
}
int getMaximumIndependentSet() { //计算最大独立集、最小团覆盖
memset(vis,0,sizeof(vis));
int res=0;
for(int i=1; i<=n; i++) {
if(!vis[order[i]]) {
res++;
vis[order[i]]=true;
for(int j=head[order[i]]; j!=-1; j=edge[j].next)
vis[edge[j].to]=true;
}
}
return res;
}
}mcs;
int main() {
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&(n+m)) {
mcs.init(n,m);
for(int i=1; i<=m; i++) {
int x,y;
scanf("%d%d",&x,&y);
mcs.addEdge(x,y);
mcs.addEdge(y,x);
}
mcs.mcs();
if(!mcs.judge())//若不为弦图
printf("No\n");
else { //若为弦图
printf("Yes\n");
int res1=mcs.getMaximumClique();//最大团、最小着色
int res2=mcs.getMaximumIndependentSet();//最大独立集、最小团覆盖
printf("The maximum clique:%d\n",res1);
printf("The maximum independent set:%d\n",res2);
}
}
return 0;
}
版权声明:本文为u011815404原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。