连通性

参考资料

• 强连通分量 - OI Wiki
• 双连通分量 - OI Wiki
• 割点和桥 - OI Wiki
• 2-SAT - OI Wiki

强连通分量（SCC）

Tarjan 算法

vector<int> G[N];
int dfn[N],low[N],sccno[N];
int cnt=0,scc_cnt=0;
stack<int> s;
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccno[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		scc_cnt++;
		while(1)
		{
			int x=s.top();
			s.pop();
			sccno[x]=scc_cnt;
			if(x==u)break;
		}
	}
}

双连通分量（BCC）

边双连通分量

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
vector<pair<int,int>> G[N];
int dfn[N],low[N],bccno[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
void tarjan(int u,int k)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	for(auto [v,i]:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}
		else if(i!=k)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		bcc_cnt++;
		while(1)
		{
			int x=s.top();
			s.pop();
			bccno[x]=bcc_cnt;
			if(x==u)break;
		}
	}
}
vector<int> ans[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back({v,i});
		G[v].push_back({u,i});
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,-1);
	}
	for(int i=1;i<=n;i++)
	{
		ans[bccno[i]].push_back(i);
	}
	cout<<bcc_cnt<<'\n';
	for(int i=1;i<=bcc_cnt;i++)
	{
		cout<<ans[i].size()<<' ';
		for(auto x:ans[i])cout<<x<<' ';
		cout<<'\n';
	}
	return 0;
}

点双连通分量

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
vector<int> G[N];
int dfn[N],low[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
vector<int> ans[N];
void tarjan(int u,int fa)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	int son=0;
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			son++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				bcc_cnt++;
				while(1)
				{
					int x=s.top();
					s.pop();
					ans[bcc_cnt].push_back(x);
					if(x==v)break;
				}
				ans[bcc_cnt].push_back(u);
			}
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(fa==0&&son==0)ans[++bcc_cnt].push_back(u);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,0);
	}
	cout<<bcc_cnt<<'\n';
	for(int i=1;i<=bcc_cnt;i++)
	{
		cout<<ans[i].size()<<' ';
		for(auto x:ans[i])cout<<x<<' ';
		cout<<'\n';
	}
	return 0;
}

2-SAT

SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 $k>2$ 时该问题为 NP 完全的。所以我们只研究 $k=2$ 的情况。

2-SAT，简单的说就是给出 $n$ 个布尔方程，每个方程和两个变量相关，如 $a\vee b$，表示变量 $a, b$ 至少满足一个。然后判断是否存在可行方案，显然可能有多种选择方案，一般题中只需要求出一种即可。另外，$\neg a$ 表示 $a$ 取反。

例题

洛谷 P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

洛谷 P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
vector<int> G[N];
int dfn[N],low[N],sccno[N];
int cnt=0,scc_cnt=0;
stack<int> s;
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccno[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		scc_cnt++;
		while(1)
		{
			int x=s.top();
			s.pop();
			sccno[x]=scc_cnt;
			if(x==u)break;
		}
	}
}
vector<pair<int,int>> E;
int deg[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		E.push_back({u,v});
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i);
	}
	for(auto [u,v]:E)
	{
		if(sccno[u]!=sccno[v])deg[sccno[u]]++;
	}
	int k=0;
	for(int i=1;i<=scc_cnt;i++)
	{
		if(deg[i])continue;
		if(k)
		{
			cout<<0<<'\n';
			return 0;
		}
		k=i;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(sccno[i]==k)ans++;
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P8436 【模板】边双连通分量

洛谷 P8436 【模板】边双连通分量

对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
vector<pair<int,int>> G[N];
int dfn[N],low[N],bccno[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
void tarjan(int u,int k)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	for(auto [v,i]:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}
		else if(i!=k)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		bcc_cnt++;
		while(1)
		{
			int x=s.top();
			s.pop();
			bccno[x]=bcc_cnt;
			if(x==u)break;
		}
	}
}
vector<int> ans[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back({v,i});
		G[v].push_back({u,i});
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,-1);
	}
	for(int i=1;i<=n;i++)
	{
		ans[bccno[i]].push_back(i);
	}
	cout<<bcc_cnt<<'\n';
	for(int i=1;i<=bcc_cnt;i++)
	{
		cout<<ans[i].size()<<' ';
		for(auto x:ans[i])cout<<x<<' ';
		cout<<'\n';
	}
	return 0;
}

洛谷 P8435 【模板】点双连通分量

洛谷 P8435 【模板】点双连通分量

对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
vector<int> G[N];
int dfn[N],low[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
vector<int> ans[N];
void tarjan(int u,int fa)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	int son=0;
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			son++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				bcc_cnt++;
				while(1)
				{
					int x=s.top();
					s.pop();
					ans[bcc_cnt].push_back(x);
					if(x==v)break;
				}
				ans[bcc_cnt].push_back(u);
			}
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(fa==0&&son==0)ans[++bcc_cnt].push_back(u);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,0);
	}
	cout<<bcc_cnt<<'\n';
	for(int i=1;i<=bcc_cnt;i++)
	{
		cout<<ans[i].size()<<' ';
		for(auto x:ans[i])cout<<x<<' ';
		cout<<'\n';
	}
	return 0;
}

洛谷 P3387 【模板】缩点

洛谷 P3387 【模板】缩点

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
vector<int> G[N],H[N];
int dfn[N],low[N],scc[N];
int cnt=0,scc_cnt=0;
stack<int> s;
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!scc[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		scc_cnt++;
		while(1)
		{
			int x=s.top();
			s.pop();
			scc[x]=scc_cnt;
			if(x==u)break;
		}
	}
}
int a[N],b[N],dp[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		b[scc[i]]+=a[i];
		for(auto j:G[i])
		{
			if(scc[i]!=scc[j])
			{
				H[scc[i]].push_back(scc[j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=scc_cnt;i++)
	{
		dp[i]=b[i];
		for(auto j:H[i])
		{
			dp[i]=max(dp[i],dp[j]+b[i]);
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P3388 【模板】割点（割顶）

洛谷 P3388 【模板】割点（割顶）

给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=20005;
vector<int> G[N];
int dfn[N],low[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
int a[N];
void tarjan(int u,int fa)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	int son=0;
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			son++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				bcc_cnt++;
				while(1)
				{
					int x=s.top();
					s.pop();
					a[x]++;
					if(x==v)break;
				}
				a[u]++;
			}
		}
		else if(v!=fa)
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(fa==0&&son==0)a[u]++;
}
vector<int> ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,0);
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]>1)ans.push_back(i);
	}
	cout<<ans.size()<<'\n';
	for(auto x:ans)cout<<x<<' ';
	return 0;
}

洛谷 P4782 【模板】2-SAT

洛谷 P4782 【模板】2-SAT

有 $n$ 个布尔变量 $x_1\sim x_n$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$x_i$ 为 true / false 或 $x_j$ 为 true / false」。例如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
vector<int> G[N<<1];
int dfn[N<<1],low[N<<1],sccno[N<<1];
int cnt=0,scc_cnt=0;
stack<int> s;
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccno[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		scc_cnt++;
		while(1)
		{
			int x=s.top();
			s.pop();
			sccno[x]=scc_cnt;
			if(x==u)break;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,x,v,y;
		cin>>u>>x>>v>>y;
		G[u+n*(1-x)].push_back(v+n*y);
		G[v+n*(1-y)].push_back(u+n*x);
	}
	for(int i=1;i<=n<<1;i++)
	{
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		if(sccno[i]==sccno[i+n])
		{
			cout<<"IMPOSSIBLE"<<'\n';
			return 0;
		}
	}
	cout<<"POSSIBLE"<<'\n';
	for(int i=1;i<=n;i++)
	{
		cout<<(sccno[i]>sccno[i+n])<<' ';
	}
	return 0;
}