连通性&割顶&桥&双连通&强连通&tarjan。。。
hicc0305
2018-04-24 09:23:30
## 概念：
### 连通分量：
连通：在无向图中，若从Vi到Vj有路径，则称Vi和Vj是连通的，而无向图有自反性、对称性和传递性，因此此时Vj和Vi也是连通的。
#### 连通分量：
Connected Component，相互可达的结点集合。
#### 连通图：
在无向图G中，若任意两个不同的顶点都连通，则G为连通图。
### 割顶和桥：
#### 割顶：
Cut Vertex，对于无向图G，如果删除某个顶点u后，连通分量数目增加，则u便是图G的关节点（Articulation Vertex）或割顶。
#### 桥：
Bridge，如果删除某条边，G就非连通了，这条边就称之为桥。
### 时间戳：
记录全局的当前时间。每个点访问的时间戳可以表示出各个点的访问顺序。
### 反向边
第一次处理时，从后代指向祖先的边称为反向边。
### 双连通分量：
#### 点-双连通：
对于一个连通图，如果任意两点至少存在两条“点不重复”的路径，
则说这个图是点-双连通的（一般简称为双连通，Biconnected）
任意两条边都在同一个简单环内，即内部无割顶
#### 边-双连通：
任意两点至少存在两条“边不重复”的路径（Edge-biconnected）
每条边都至少在一个简单环中，即所有边都不是桥
#### 双连通分量：
对于无向图，点-双连通的极大子图成为双连通分量（Biconnected Component，BCC）或块（Block）
每条边恰好属于一个双连通分量
不同连通分量可能会有公共点（最多也只有一个公共点），这也就是割顶
任意一个割顶都是至少两个不同双连通分量的公共点
#### 边-双连通分量：
边-双连通的极大子图
桥不属于任何一个边-双连通分量
其他边恰好属于一个边-双连通分量
点-双连通分量：{A,C,D}和{B,C,E}
边-双连通分量：{A,C,B,E,D}
### 强连通
强联通：在有向图中，若Vi到Vj有路径，Vj到Vi也有路径，则叫Strongly Connected Component， SCC。
强连通分量：强联通的极大子图
## TIP：双连通为无向图，强连通为有向图
------------
------------
## 程序
几个数组的概念：
pre:记录当前节点的时间戳
low:low[x]为x及其后代所能通过反向边连回的最早的祖先的pre值
则若节点u的子节点v的low[v]≤pre[u]，u是割顶
若low[v]>pre[u]，即v的后代只能连回v自己，那么只需删除(u,v)这条边就可以让G非连通了，这条边就是桥。当然u也是割点
### 求割顶和桥：
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cnt=0,tot=0,num=0;
int head[200100],nxt[200100],to[200100];
int low[100100],f[100100],pre[100100];
void addedge(int x,int y)
{
cnt++;
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
}
void dfs(int u,int fa)
{
int ch=0;
low[u]=pre[u]=++tot;
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(!pre[v])//若v还未访问过
{
ch++;
dfs(v,u);//继续dfs求出low[v]
low[u]=min(low[u],low[v]);
if(low[v]>=pre[u]) f[u]=1;//low[v]>=pre[u] 则为割顶
if(low[v]>pre[u]) num++;//low[v]>pre[u] 则为割顶
}
else if(pre[v]<pre[u] && v!=fa) low[u]=min(low[u],pre[v]);//v已经访问过，并且比u先访问到，如果不是u的父亲节点，low[u]就可以更新
}
if(fa==0 && ch==1) f[u]=0;//若u为根节点并且只有一个子节点把根节点去掉不会多出连通分量，所以u不为割顶
}
int main()
{
while(1)
{
memset(f,0,sizeof(f));
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
cnt=0,tot=0,num=0;
scanf("%d%d",&n,&m);
if(!n && !m) break;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for(int i=1;i<=n;i++)
if(!pre[i]) dfs(i,0);
int ans=0;
for(int i=1;i<=n;i++)
if(f[i]) ans++;
cout<<ans<<" "<<num<<endl;//ans是割顶数量，num是桥的数量
for(int i=1;i<=n;i++)
if(f[i]) cout<<i<<endl;
}
return 0;
}
```
### 求双联通分量
代码其实差不多，这种方法求双联通分量叫做tarjan
```cpp
int bcc_cnt; //点_双连通分量的数目
int belong[maxn]; //节点属于的点_双连通分量的编号
vector<int> G[maxn], bcc[maxn]; //点_双连通分量
int tarjan(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock, child = 0;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i]; Edge e = Edge(u, v);
if (!pre[v])
{
s.push(e); child++;
int lowv = tarjan(v, u); lowu = min(lowu, lowv); //用后代更新lowu
if(lowv >= pre[u])
{
iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear();
while(1)
{
Edge x = s.top(); s.pop();
if (belong[x.u] != bcc_cnt)
{
bcc[bcc_cnt].push_back(x.u);//x.u在第bbc_cnt个双连通分量中
belong[x.u] = bcc_cnt;//x.u所在的双连通分量的编号是bcc_cnt
}
if (belong[x.v] != bcc_cnt)
{
bcc[bcc_cnt].push_back(x.v);
belong[x.v] = bcc_cnt;
}
if (x.u == u && x.v == v) break;
}
}
}
else if (pre[v] < pre[u] && v != fa)
{
s.push(e);
lowu = min(lowu,pre[v]);
}
}
if (fa < 0 && child == 1) iscut[u] = 0;
return lowu;
}
```
### 求强联通分量
代码其实也差不多一样，而且算法也叫tarjan。。。总之Tarjan是个很六的人
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans=0;
int sta[200001],top=0;
int dfn[200001],low[200001],tot=0;
int head[200001],nxt[200001],to[200001],cnt=0;
int f[200001];
void addedge(int x,int y)//邻接链表存图
{
cnt++;
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
}
void tarjan(int u)//tarjan求强联通分量
{
f[u]=1;
dfn[u]=low[u]=++tot;
sta[++top]=u;//入栈
for(int i=head[u];i!=0;i=nxt[i])
{
int v=to[i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(f[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
ans++;
do
{
f[sta[top]]=0;
}while(sta[top--]!=u);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
addedge(i,a);//加边，是有向边，别加两次
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
cout<<ans;//强连通分量的数量
return 0;
}
```