跳到主要内容

连通性

参考资料​

强连通分量（SCC）​

Tarjan 算法​

413 Bcpp
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）​

边双连通分量​

965 Bcpp
#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;
}

点双连通分量​

996 Bcpp
#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>2k>2 时该问题为 NP 完全的。所以我们只研究 k=2k=2 的情况。

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

例题​

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

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

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

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

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

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

洛谷 P3387 【模板】缩点

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

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

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

给出一个 nn 个点，mm 条边的无向图，求图的割点。

洛谷 P4782 【模板】2-SAT

有 nn 个布尔变量 x1∼xnx_1\sim x_n，另有 mm 个需要满足的条件，每个条件的形式都是「xix_i 为 true / false 或 xjx_j 为 true / false」。例如「x1x_1 为真或 x3x_3 为假」、「x7x_7 为假或 x2x_2 为假」。

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