爵士OIer查看:2 回复:8 评论:2 创建时间:2020-05-09T11:00:02用户:爵士OIer查看:2 回复:8 评论:2 创建时间:2020-05-09T11:00:02
本篇会比二分图短一些，大家可以安心（不必受长文煎熬了）。
连通性
若存在一条从结点u到结点v的路径，则称u和v连通。
一个图中，任意两点都连通，则称这个图为连通图。
图的一个极大连通子图，称为连通分量，在有向图中称为强连通分量。
连通性：Warshall算法
将Floyd算法的d[u][v]改为记录u是否能到达v。
可以在O(|V|^3 )的时间里，得到任意两点之间的连通信息。
Code:
bool d[maxn][maxn];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(w[i][j])
d[i][j]=true;
else
d[i][j]=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(d[j][i]&&d[i][k])
d[j][k]=true;
连通性：遍历算法
从一个点u开始遍历，若到达了点v，那么u连通v。那么从每个点开始遍历，即可得到任意两点间是否连通。O(|V|∗|E|)
在无向图中，连通具有传递性，被其他点遍历到了的点，可以不用重新遍历。O(|V|+|E|)
并查集(Disjoint Set Union,DSU)
定义：若干个元素，每个元素属于且只属于一个特定的集合。
并查集是一个可以维护这种信息的数据结构，支持查询元素的集合、合并两个集合。
并查集本身是一个森林，可以用一个数组表示，记录每个元素的父亲（值为本身，表示该元素为树根）。
不妨用树根表示每个集合，那么查询元素所属的集合，只需寻找所在树的根。
合并两个集合，相当于把两棵树合并。
int dsu[maxn];
void init(){
for(int i=1;i<=n;i++)
dsu[i]=i;
}
int find(int pos){
if(dsu[pos]==pos)return pos;
else return find(dsu[pos]);
}
void merge(int x,int y){
dsu[find(x)]=find(y);
}
注意到：
记录每个集合的大小，在合并时，将较小集合并入较大集合，可以使得树变得平衡。合并和查询复杂度为O(log|V|)
在无需撤回操作时，使用路径压缩的技巧，复杂度降为O(α(|V|)) （反阿克曼函数，比log还小）
Code：
int dsu[maxn],size[maxn];
void init(){
for(int i=1;i<=n;++i)dsu[i]=i,size[i]=1;
}
int find(int pos){
if(dsu[pos]==pos)return pos;
else return dsu[pos]=find(dsu[pos]);
}
void merge(int x,int y){
x=find(x);y=find(y);
if(size[x]<size[y])swap(x,y);
dsu[y]=x;size[x]+=size[y];
}
例题：模板
输入格式
第一行包含两个整数 N,M，表示共有 N 个元素和 M 个操作。
接下来 M 行，每行包含三个整数 Z_i,X_i,Y_i 。
当 Z_i=1 时，将 X_i 与 Y_i 所在的集合合并。
当 Z_i=2 时，输出 X_i 与 Y_i是否在同一集合内，是的输出 Y ；否则输出 N 。
输出格式
对于每一个 Z_i=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。<button class="copy-btn lfe-form-sz-middle" type="button" data-v-370e72e2="" data-v-52f2d52f=""></button>
输入
4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4输出
N Y N Y
说明
对于 30% 的数据，N≤10，M≤20 。
对于 70% 的数据，N≤100，M≤10^3。
对于 100\%100% 的数据，1≤N≤10^4，1≤M≤2×10^5 。
Code：
#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,s,zuiz,f[10010],aa,bb,cc;
int ffff(int k);
int main(){
cin>>n>>m;
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++){
cin>>aa>>bb>>cc;
if(aa==1) f[ffff(bb)]=ffff(cc);
else if(ffff(bb)==ffff(cc))printf("Y\n");
else printf("N\n");
}
return 0;
}
int ffff(int k){
if(f[k]==k)return k;
return f[k]=ffff(f[k]);
}
有向图强连通分量（strongly connected components）
一个有向图被是称为是强连通的当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径，也存在从 v 到 u 的路径。有向图 的极大强连通子图(这里指点数极大)被称为强连通分量。
看下图。
比如说这个有向图中，点 1,2,4,5,6,7,8 和相应边组成的子图就是一 个强连通分分量，另外点 3和点9单独构成强连通分量。
在介绍求解强连通分量的算法之前先来介绍一下搜索树。
有向图的搜索树主要有 4 种边(这张图只有三种)，其中用实线画出来的是树边，每次搜索找到一个还没有访问过的结点的时候这就形成了了 一条树边。 用长虚线画出来的是回边。 用短虚线画出来的是横叉边，它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个 结点并不是当前节点的祖先时形成的。除此之外，像从 1 到 6 这样的 边叫做前向边，它是在搜索的时候遇到子树中的结点的时候形成的。
理解搜索树中的概念是求强连通分量的基础。
Tarjan 算法
Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的算法。它可以在 O(n + m) 的时间内得出结果。
Tarjan 算法主要是利用 DFS 来寻找强连通分量的。现在我们来看看在 DFS 的过程中强连通分量有什么性质。
很重要的一点是如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点(这通常被称为这个强连通分量的根)。
Tarjan 算法主要是在 DFS 的过程中维护了一些信息：dfn,low 和一个栈
栈里的元素表示的是当前已经访问过但是没有被归类到任一强连通分量的结点。
dfn[u] 表示结点 u 在 DFS 中第一次搜索到的次序，通常被叫做时间戳。
low[u] 稍微有些复杂，它表示从 u 或者以 u 为根的子树中的结点，再通过一条反祖边或者横叉边可以到达的时间戳最小的结点 v 的时间戳，并且要求 v 有一些额外的性质: v 还要能够到达 u。
可以证明，结点 u 是某个强连通分量的根等价于 dfn[u] 和 low[u] 相等。
当通过 u 搜索到一个新的节点 v 的时候可以有多种情况:
结点 u 通过树边到达结点 v
low[u] = min(low[u], low[v])
结点 u 通过反祖边到达结点 v，或者通过横叉边到达结点 v 并且满足 low 定义中 v 的性质
low[u] = min(low[u], dfn[v])
Code：
例题：受欢迎的牛
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 A 喜欢 B，B 喜欢 C，那么 A 也喜欢 C。牛栏里共有 N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
输入格式
第一行：两个用空格分开的整数：N 和 M。
接下来 M 行：每行两个用空格分开的整数：A 和 B，表示 A 喜欢 B。
输出格式
一行单独一个整数，表示明星奶牛的数量。
输入输出样例 输入
3 3 1 2 2 1 2 3输出
1
解析:
首先，不难发现，如果这所有的牛都存在同一个强联通分量里。那么它们一定互相受欢迎。
那么，我们怎么来找明星呢。
很简单，找出度为0的强联通分量中的点。这样可以保证所有的人都喜欢它，但是它不喜欢任何人，所以说不存在还有人事明星。
此题还有一个特殊情况：
如果有两个点分别满足出度为零的条件，则没有明星，这样无法满足所有的牛喜欢他。
有了上边的解释，题目就不是那么难了。
Code：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int maxn=1e4+5;
const int maxm=5e4+5;
int to[maxm],nex[maxm],fir[maxn];
int col,num,dfn[maxn],low[maxn],de[maxn],si[maxn];
int tot=0,co[maxn],n,m;
int top,st[maxn];
template<class T> inline void read(T &x)
{
x=0;
register char c=getchar();
register bool f=0;
while (!isdigit(c)) f ^=c=='-',c=getchar();
while (isdigit(c)) x=x*10+c-'0',c=getchar();
if(f)x=-x;
}
template <class T> inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
inline void ins(int x,int y)
{
to[++tot]=y;
nex[tot]=fir[x];
fir[x]=tot;
}
void Tarjan(int u)
{
dfn[u]=low[u]=++num;
st[++top]=u;
for(int i=fir[u];i;i=nex[i])
{
int v=to[i];
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!co[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
co[u]=++col;
++si[col];
while(st[top]!=u)
{
++si[col];
co[st[top]]=col;
--top;
}
--top;
}
}
int main()
{
int x,y;
read(n);read(m);
for(ri i=1;i<=m;i++)
{
read(x);read(y);
ins(y,x);
}
for(ri i=1;i<=n;i++)
if(!dfn[i])Tarjan(i);
for(ri i=1;i<=n;i++)
for(ri j=fir[i];j;j=nex[j])
if(co[i]!=co[to[j]])de[co[to[j]]]++;
int ans=0,u=0;
for(ri i=1;i<=col;i++)if(!de[i])ans=si[i],u++;
if(u==1)print(ans);
else print(0);
return 0;
}
拓展：无向图的割点与桥
割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点称为割点。
桥（割边）：无向联通图中，去掉一条边，图中的连通分量数 增加，则这条边，称为桥或者割边。
割点与桥（割边）的关系：
1.有割点不不一定有桥,有桥一定存在割点
2.桥一定是割点依附的边。
解法：
朴素的做法就是枚举删掉一个点或者边，然后判断整张图是否连 通。
非根节点 u 是图 G 的割点，当且仅当 u 存在一个子节点 v，使 得 v 及其后代都没有反向边连向u的祖先。
即非根节点 u 是图 G 的割点当 u 存在一个子节点 v，使得 low[v] >= dfn[u]。
严格大于就是桥的情况。
这里要注意有向图和无向图 Tarjan 算法的区别，有向图 Tarjan 需要 inq 数组来判断一条边是不是反祖边，无向图则不需要，因为横叉边也会成环。
