本文主要是介绍图的连通性相关总结：强连通，双连通，割点割边，2-sat，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
刚学完了连通性相关的知识，总结一下
以下均使用tarjan算法
强联通分量
定义
强连通分量即强联通子图，一般我们都在有向图中求取最大强连通分量，即有向图一张图中任两点可达的最大子图。其中单独一个点也是强联通子图。
算法
在这里我们使用tarjan算法，维护两个栈，系统堆栈（递归隐式使用），连通子图堆栈。维护两个数组，dfn时间戳数组和low最早可达（自己取的名字）数组。
算法过程如下：
对每一个联通块调用tarjan函数，他的运行和dfs类似，会给访问到的节点打上时间戳，并把所有经过节点加入栈中。同时维护low数组，low数组取自己dfn，子树dfn，可过一条非树边到的栈中节点dfn最小值。
如果在某点遍历完所有边后发现其dfn==low，那么说明它的子树全都无法到达自己以上的节点，那么出栈直到u出栈，取出的所有节点为一个强连通分量（不用担心有无法到达根的子树结点，如果它无法到达，它的low应该等于自己或者某个介于根dfn和它dfn的中间值，那么他一定会在根节点判定之前作为另一个连通分量出栈）。根据需要可以打标记、加入集合输出等等。
缩点
缩点意为跑出scc后，将所有强联通子图看作一个整体，那么最终得到的是一张DAG即有向无环图，可以统计新图的入度，出度等信息。
割点，割边
割点
定义
无向图，删去这一点，联通块个数++
算法
还是tarjan算法，还是差不多的low和dfn数组，注意low数组定义为不经过其父亲到达的最小时间戳，因为是无向图，为了防止向回走需要在递归时传递父节点。
对于边u-v，如果在回溯后发现low[v]>=dfn[u]，说明u是到达v的唯一途径，那么u可能是（反例见下）割点，标记上即可。
如果都按这么标记，那么可以肯定的是最早调用tarjan的根节点一定是被标记为割点的，我们分析一下，如果根节点连接了两个或以上的子树，那么他的确是割点，但如果根节点只有一个子树，那么根节点不是割点。所以记录下子树个数，特判即可。
割边
定义
割边也叫桥，意为删边后连通块个数++。
算法
还是tarjan，和割点类似，只不过low[v]>=dfn[u]改为low[v]>dfn[u]，同时不用特判根节点，即可。至于记录问题，可以用< father ,x >代表或者在前向星图中对x,x^1边打标记，具体如何看题目需要。
双联通分量
点双联通分量
定义
点双联通子图意为无向图该子图内任意两点有两条不相交路径。等价于任意两点在一个环上。
算法
tarjan again。
在求割点（根节点不特判）的基础上维护一个栈，在找到割点u后出栈直到栈顶为割点u，取出的点和u自己作为一个点双联通。（不取出u是因为一个割点可能属于多个点双联通）。
边双连通分量
定义
对于边u-v，如果删去任意一条边都不会使u-v不连通，我们称之为边连通
算法
tarjan。
求桥边，删去桥边每个单独联通块为一个边双连通。
2-SAT算法
问题模型
若干个命题pi。给出任意个关系<a,b>代表逻辑关系。a and b =x，a or b=x(x属于{0,1})等等。求满足所有条件的成真赋值。
算法过程
我们将n个命题建立2n个点，1-n为真，2-n为假（类似拓展并查集）。我们在这个图中分析逻辑关系。如果是a or b=1，显然有 !a->b且!b->a，如果是a xor b=0，显然有!a->!b,a->b,b->a,!b->!a。我们对每一个蕴含等值式，由前件向后件连单向边。
如果存在某一命题一定取某值，比如a一定取1，那么就有!a->a，意即如果取!a，一定取a，那么会产生矛盾，也就是无法取!a。
我们现在是选择n个命题的取值，对应到图中是恰选出n个点（一个命题就一个），且他们对其余点无法到达（为什么呢？因为边是蕴含关系，如果起点被选中了，那么终点一定也被选中）。可以对这个图求强连通分量。在同一个分量内要么全不取，要么全取（显然）。那么如果i和i+n（即pi和pi的非）在同一个分量内，也就说明他们一定要被同时选取，那么肯定是不满足条件的，无成真命题。
如果说满足条件，我们怎么取值呢？考虑关系A->B->!A。意为若A则B，若B则非A。那么我们断不能取A，而是要取非A。也就是我们尽量取这个有向图靠近“终点”的那一侧。我们知道求取强联通后缩点得到的DAG是可以拓扑排序的，我们对他拓扑排序，每一个命题取其拓扑序靠后的就可以了。
当tarjan算法完成后，我们其实已经对图做了一次拓扑排序了。我们对每个强连通分量的编号就是逆着的拓扑序。所以我们对i号命题，如果sc[i]<sc[i+n]，即取1，反之取0.
例题
链接
洛谷P5782
题意
议会中每个团队恰两人，从每个团队选一个人参与委员会，给出多个关系<u,v>意为uv不能同时参与委员会，求可行方案。
思路
我们如此思考就是一个标准的2-SAT了。
- 议会中一个队两人，对应取值真或假。
- 委员会一定要有一个人，意为最终合取式都要出现。
- 若干对排斥关系。如果a排斥b，因为每个队都要出人，那么a->非b，b->非a显然成立。
满足2-sat条件，套板子即可。
代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=2e6+5;const int maxe=2e6+5;const int inf=0x3f3f3f3f;int dfn[maxn],low[maxn],dfncnt; bool in_stack[maxn];int scc[maxn],sc;//强联通也就是逆拓扑int cnt;int head[maxe];struct Edge{int next;int to;} edge[maxe]; void init(){memset(head,-1,sizeof(head));}void add(int u,int v){edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}int sta[maxn],top;void tarjan(int u) {low[u] = dfn[u] = ++dfncnt;sta[++top]=u;in_stack[u] = 1;for (int i = head[u]; ~i; i = edge[i].next) {int v = edge[i].to;if (!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]);} else if (in_stack[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {++sc;while (1) {int now=sta[top--];scc[now] = sc;in_stack[now] = 0;if(now==u){break;}}}}int main(){#ifndef ONLINE_JUDGEfreopen("D:\\code\\IO\\in.txt","r",stdin);freopen("D:\\code\\IO\\out.txt","w",stdout);#endifIOSint n,m;cin>>n>>m;init();while(m--){int a,b,pa,pb,ra,rb;cin>>a>>b;pa=(a-1)/2,pb=(b-1)/2;//a属于第pa+1个党派ra=(a%2)+1+2*pa,rb=(b%2)+1+2*pb;//变幻到相反命题add(a,rb);add(b,ra);}for(int i=1;i<=2*n;i++)if(!dfn[i]) tarjan(i);for(int i=1;i<=n;i++){int a=2*i-1,b=a+1;if(scc[a]==scc[b]){cout<<"NIE"<<endl;return 0;}}for(int i=1;i<=n;i++){int a=2*i-1,b=a+1;if(scc[a]<scc[b])cout<<a<<endl;elsecout<<b<<endl;}return 0;}这篇关于图的连通性相关总结：强连通，双连通，割点割边，2-sat的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
