无向图最大独立集问题题解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+16;
vector<pair<int,int>>G[N];
int tsp,dfn[N],low[N];
int fa[N],f[N][2],ff[N][2];

void dp(int x, int y) {
    int cnt;
    cnt=0;
    for(int i=y;i!=fa[x];i=fa[i]){cnt++;ff[cnt][0]=f[i][0];ff[cnt][1]=f[i][1];}
    for(int i=2;i<=cnt;i++){
        ff[i][0]+=max(ff[i-1][0],ff[i-1][1]);
        ff[i][1]+=ff[i-1][0];
    }
    f[x][0]=ff[cnt][0];

    cnt=0;
    for(int i=y;i!=fa[x];i=fa[i]){cnt++;ff[cnt][0]=f[i][0];ff[cnt][1]=f[i][1];}
    ff[1][1]=-0x3f3f3f3f;
    for(int i=2;i<=cnt;i++){
        ff[i][0]+=max(ff[i-1][0],ff[i-1][1]);
        ff[i][1]+=ff[i-1][0];
    }
    f[x][1]=ff[cnt][1];
}

void tarjan(int x, int in_id) {
    low[x]=dfn[x]=++tsp;
    f[x][1]=1,f[x][0]=0;
    for(auto i:G[x])if(i.second!=in_id) {
        int y=i.first,id=i.second;
        if(!dfn[y]) {
            fa[y]=x;
            tarjan(y,id);
            low[x]=min(low[x],low[y]);
        } else low[x]=min(low[x],dfn[y]);
        
        if(dfn[x]<low[y]) {
            f[x][1]+=f[y][0];
            f[x][0]+=max(f[y][0],f[y][1]);
        }
    }

    for(auto i:G[x])if(i.second!=in_id) {
        int y=i.first;
        if(fa[y]!=x&&dfn[x]<dfn[y]) dp(x,y);
    }
}

int main() {
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++) {
        scanf("%d%d",&x,&y);
        G[x].push_back({y,i});
        G[y].push_back({x,i}); // 建图，存储边的id避免重复访问
    }
    tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    int ans=0;
    for(int i=1;i<=n;i++)if(!dfn[i]) {
        tarjan(i,0);
        ans+=max(f[i][0],f[i][1]); // 累加各连通分量最大独立集
    }
    printf("%lld",ans);
    return 0;
}

解题思路

1. 问题分析：无向图最大独立集问题，要求选出最多顶点使任意两顶点不相邻。
2. 算法选择：结合Tarjan算法与动态规划，利用双连通分量分解图结构。
3. 核心步骤：
   • Tarjan算法：求图的桥，将图分解为双连通分量（块）与树结构（块树）。
   • 动态规划：f[x][0]表示不选顶点x时的最大独立集，f[x][1]表示选顶点x时的最大独立集。
   • 状态转移：对每个双连通分量，通过dp函数处理路径节点，合并子树状态。
4. 复杂度：Tarjan算法O(n+m)，动态规划O(n)，整体复杂度O(n+m)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<pair<int,int>>G[N];
int tsp,dfn[N],low[N];
int fa[N],f[N][2],ff[N][2];
void dp(int x,int y)
{
    int cnt;
    cnt=0;
    for(int i=y;i!=fa[x];i=fa[i]){cnt++;ff[cnt][0]=f[i][0];ff[cnt][1]=f[i][1];}
    for(int i=2;i<=cnt;i++)
    {
        ff[i][0]+=max(ff[i-1][0],ff[i-1][1]);
        ff[i][1]+=ff[i-1][0];
    }
    f[x][0]=ff[cnt][0];

    cnt=0;
    for(int i=y;i!=fa[x];i=fa[i]){cnt++;ff[cnt][0]=f[i][0];ff[cnt][1]=f[i][1];}
    ff[1][1]=-0x3f3f3f3f;//相当于选y点的状态是坏的，不会被后来的状态所继承
    for(int i=2;i<=cnt;i++)
    {
        ff[i][0]+=max(ff[i-1][0],ff[i-1][1]);
        ff[i][1]+=ff[i-1][0];
    }
    f[x][1]=ff[cnt][1];
}

void tarjan(int x,int in_id)
{
	low[x]=dfn[x]=++tsp;
	f[x][1]=1,f[x][0]=0;
	for(auto i:G[x])if(i.second!=in_id)
	{
		int y=i.first,id=i.second;
		if(!dfn[y])
		{
			fa[y]=x;
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
		}
		else
			low[x]=min(low[x],dfn[y]);
		
		if(dfn[x]<low[y])
		{
			f[x][1]+=f[y][0];
			f[x][0]+=max(f[y][0],f[y][1]);
		}
	}

	for(auto i:G[x])if(i.second!=in_id)
	{
		int y=i.first;
		if(fa[y]!=x&&dfn[x]<dfn[y])
		{
			dp(x,y);
		}
	}
}

int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back({y,i});
		G[y].push_back({x,i});
	}
	tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    int ans=0;
	for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,0),ans+=max(f[i][0],f[i][1]);
	printf("%lld",ans);
	return 0;
}