Tarjan算法与无向图连通性
Tarjan算法求割点与割边
定义与性质：
定义
给定无向连通图\(G=(V,E)\)
- 割点：节点\(x\in V\),若将节点\(x\)及其所相连的所有边删去之后，图\(G\)分成两个及以上子图，则称节点\(x\)为图\(G\)的割点
- 割边: 也称桥，边\(i\in E\),若将边\(i\)在图中删去，会使得图\(G\)分成两个不相连的子图，则称\(i\)为图\(G\)的桥
- 点双连通图：若图\(G\)不含有割点，则称图\(G\)为点双连通图
- 边双连通图：若图\(G\)不含有割边，则称图\(G\)为边双连通图
- 点双连通分量：图\(G\)的极大点双连通子图被称为图\(G\)的点双连通分量，简称"\(v-DCC\)"(极大的意思即不存在更大的)
- 边双连通分量：图\(G\)的极大边双连通子图被称为图\(G\)的边双连通分量,简称"\(e-DCC\)"
- 5、6统称为双连通分量，简称\(DCC\)，一张无向图的割点与割边就是各个连通块的割点割边的总和
性质： - 一个简单环上的节点一定不是割边
- 一个无向图是点双连通图，当且仅当满足以下条件之一：(1).图中节点数不超过2.(2)图中的任意两个点都至少被包含在一个简单环中
- 一张无向图是边双连通图，当且仅当每一条边都在一个简单环中
- 在一个点双连通图中(节点数大于2)，任意两个节点都有着至少两条互不相交的路径
- 在一个边双连通图中，每一条边的两个端点都有另一条路线可以抵达对方
- 若某个点双连通分量中的两个节点被一个奇环所包含，则每一对节点都被至少一个奇环包含
Tarjan算法
tarjan算法可以在线性时间内求出一张图的所有割点与割边
具体是这样的
tarjan算法需要记录一个时间戳(\(dfn\))和追溯值(\(low\))
我们按照深度优先遍历的方法，每个节点只访问一次，形成一颗搜索树.
我们定义\(s(u)\)表示\(u\)节点的子树节点集合(\(u\in s(u)\))，则\(low(u)\)值为以下节点的时间戳的最小值
- 属于\(s(u)\)的节点
- 设一个节点\(v\in s(u)\)，通过不在搜素树上的一条边能够抵达\(v\)的节点
以下图为例，我们使用加粗代表搜索树，黑笔代表时间戳，红笔代表追溯值
对于\(low\)的计算，根据定义，我们应该先令\(low[u]=dfn[u]\)，然后扫描\(u\)的每一条出边\((u,v)\) - \((u,v)\)是搜索树上的边，此时令\(low[u]=\min(low[u],low[v])\)
- \((u,v)\)不是搜索树上的边，此时令\(low[u]=\min(low[u],dfn[v])\)
void tarjan(int u,int in){
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if((i^1)!=in)low[u]=min(low[u],dfn[v]);
}
}
割边判定法则
边\((u,v)\)是桥，当且仅当搜索树上\(u\)的子节点\(v\)满足
\[dfn[u]<low[v] \]证明：简单证明，\(low[v]\)代表的是能到达\(v\)节点的节点的时间戳的最小值，若仍大于\(dfn[u]\)则代表能到\(v\)节点的全是\(u\)节点子树中的节点，因为子树中的节点的时间戳才会大于\(dfn[u]\)，于是\(v\)与\(u\)的子树形成了一个封闭的环境，将\((u,v)\)删去之后\(v\)没有任何一条边可以到\(u\)这边的连通块，于是边\((u,v)\)是桥
对于程序的实现，我们因为无向图采用双向边，于是需要特判父亲节点，此时我们一般是记录节点的入边的编号，利用成对变换判断父节点
int dfn[N],low[N],n,m,head[N],nxt[M],ver[M],bridge[M],num,tot=1;
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void tarjan(int u,int in){
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
bridge[i]=bridge[i^1]=1;
}
}
else if((i^1)!=in)low[u]=min(low[u],dfn[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);//若图不是无向连通图
for(int i=2;i<=tot;i++)printf("%d ",bridge[i]);
}
割点判定法则
节点\(u\)是割点，当且仅当节点\(u\)满足有一个子节点\(v\)，使得
\[dfn[u]\le low[v] \]特别的，若\(u=root\)，则\(u\)是割点当且仅当有两个及其以上的子节点满足以上条件，在我们上面的图中，时间戳为6的节点就是一个割点
因为判定法则是\(\le\)号，于是不需要考虑父节点的影响，直接莽就完了
int dfn[N],low[N],n,m,head[N],nxt[M],ver[M],vis[N],num,tot=1,root;
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void tarjan(int u){
dfn[u]=low[u]=++num;
int cnt=0;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
cnt++;
if(u!=root||cnt>1)vis[u]=1;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++)if(!dfn[i])root=i,tarjan(i);
for(int i=1;i<=n;i++)printf("%d ",vis[i]);
}
双连通分量
边连通分量
求法
根据定义，我们只需要将原无向图中所有的桥删去，然后进行深度优先遍历整个图，剩下的所有连通块都是原图的一个边连通分量
//深度优先遍历的代码
void dfs(int u){
c[u]=edcc;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(c[v]||bridge[i])continue;
dfs(v);
}
}
//主函数中的代码
for(int i=1;i<=n;i++)if(!c[i])++edcc,dfs(i);
//最终我们就得到了edcc个边连通分量，其中每个节点属于的边连通分量的编号就是c
点连通分量
这个较为复杂，与边连通分量不同的是，点连通分量的割点可能会属于多个\(v-DCC\),下面举一个例子便可以说明
其中1，6两个节点便是割点
我们发现，除了割点之外，所有的点都只属于一个\(v-DCC\),只有割点不同
为了求出\(v-DCC\)，我们需要在tarjan算法的过程中维护一个栈来保存\(v-DCC\),详细的说，对于这个栈，我们进行以下操作
- 递归到节点\(u\)，将其入栈
- 若割点判定法则\(dfn[u]\le low[v]\)成立，无论\(u\)是否是根节点，都要不断弹出栈中节点直到\(v\)节点被弹出，然后再将\(u\)压入栈，所有弹出的节点与\(u\)构成一个\(v-DCC\),
void tarjan(int x) {
dfn[x] = low[x] = ++num;
stack[++top] = x;
if (x == root && head[x] == 0) { // 孤立点
dcc[++cnt].push_back(x);
return;
}
int flag = 0;
for (int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x]) {
flag++;
if (x != root || flag > 1) cut[x] = true;
cnt++;
int z;
do {
z = stack[top--];
dcc[cnt].push_back(z);
} while (z != y);
dcc[cnt].push_back(x);
}
}
else low[x] = min(low[x], dfn[y]);
}
}
缩点
e-DCC的缩点
很简单，求出所有的\(e-DCC\),然后将每一对原本有边的节点，若不在同一个\(e-DCC\)中，则将分别所属的两个\(e-DCC\)连边，实质上，这条边就是一个桥，最后会构成一棵树(若原无向图不连通则构成森林)
void add_v(int u,int v){
vnxt[++vtot]=vhead[u],vver[vhead[u]=vtot]=v;
}
//主函数中代码
vtot=1;
for(int i=2;i<=tot;i++)if(bridge[i])add_v(c[ver[i]],c[ver[i^1]]);
v-DCC的缩点
因为各个割点会在可能会出现在多个\(v-DCC\)中，于是我们将每一个割点独立出来，单独和各个包含该割点的\(v-DCC\)连边，最后仍然构成一棵树(森林)
连通分量的综合运用
冗余路径
为了从 \(F\) 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。
奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。
每对草场之间已经有至少一条路径。
给出所有 \(R\) 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。
两条路径相互分离，是指两条路径没有一条重合的道路。
但是，两条分离的路径上可以有一些相同的草场。
对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。
分析
简单来说本题题意就是在一张无向连通图中加边，使得整个无向连通图变成一个边双连通图
我们先对整张图求\(e-DCC\)进行缩点，成为一颗树，我们的目的就是在这棵树里面进行加边，使得整棵树变成一个边双连通图，求最少加边数
正确性很显然，当这棵树成了边双连通图后原图上所有的\(e-DCC\)都与其他\(e-DCC\)在至少一个简单环上，根据定义，所有的原图上的\(e-DCC\)就构成了一个边双连通图
而在一棵树上加边就会多出一个环，我们的目的就是让树上所有的点对都在至少一个环内。
引理
将一棵树变成一个边双连通图，至少需要\(\lceil\frac{cnt}{2} \rceil\),其中\(cnt\)表示叶子节点的数量
证明
先证必要性
从叶子节点入手，因为叶子节点的特殊性，对于每一次加边操作，我们最多使得两个叶子节点相连通，这一点很显然，因为只有加入的边的一端连向一个叶子节点，这个叶子节点才会在环中，所以每一次最多可以令两个叶子节点加入环，所以最少需要加入\(\lceil\frac{cnt}{2} \rceil\)条边
再证充分性
因为必要性的证明，很容易发现，最优策略加边都是从两个叶子节点处加边，那么我们需要证明这样的操作一定可以覆盖整棵树
每一个叶子节点到根的路径都是一条链，整棵树就是由所有的链组成的(重复部分只算一次)。每一次进行加边操作，假设连接的是叶子节点\((u,v)\)，那么原本树上\(u-v\)的路径就会形成一个环，因为环具有可重叠性，我们完全可以强制性要求\(lca(u,v)=1\)，若\(cnt\)是奇数，那么最后一组便由一个叶子节点再加上根节点组成，在最优情况下，每一次我们都可以消掉根节点到叶子节点的两条链，所以我们需要证明的命题就变成了对于所有的叶子节点，一定存在一种配对方式，使得每一对两个节点的最近公共祖先都是根节点，这个很显然，因为是无向图，所以不会出现根节点度数为1的极端情况(除非只有两个点)，在这棵树尽量均衡的情况下，我们可以将根节点分出去的各个子树所产生的叶子节点与其他子树的叶子节点配对，一定可以全部配对完成(若有奇数个则最后一个与根节点配对)，于是在\(\lceil\frac{cnt}{2} \rceil\)我们可以消去根节点所在的所有链，故充分性成立，原命题成立
于是证明完成之后我们的问题就变成了统计有多少个连通块是缩点之后的叶子节点，无根树的叶子节点就是度数为1的节点，在这种情况下，我们并不需要将缩点后的图建立出来，直接统计就可以了
int head[N],nxt[M],ver[M],c[N],dfn[N],low[N],tot=1,dcc,num,bridge[M],n,m,cnt,in[N];
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void tarjan(int u,int in){
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
bridge[i]=bridge[i^1]=1;++cnt;
}
}
else if(in!=(i^1))low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u){
c[u]=dcc;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(c[v]||bridge[i])continue;
dfs(v);
}
}//板子
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
for(int i=1;i<=n;i++){
if(!c[i])dcc++,dfs(i);
}
for(int i=2;i<=tot;i++){
if(bridge[i])in[c[ver[i]]]++;//度数统计
}
int ans=0;
for(int i=1;i<=dcc;i++)if(in[i]==1)ans++;
printf("%d\n",(ans+1)/2);
}
无向图必经点与必经边
必经边
例题(裸题)：逃不掉的路
现代社会，路是必不可少的。
共有 n 个城镇，m 条道路，任意两个城镇都有路相连，而且往往不止一条。
但有些路年久失修，走着很不爽。
按理说条条大路通罗马，大不了绕行其他路呗——可小撸却发现：从 a 城到 b 城不管怎么走，总有一些逃不掉的必经之路。
他想请你计算一下，a 到 b 的所有路径中，有几条路是逃不掉的？
分析
回想起边连通分量的定义，在一个边连通分量里任意两个点都具有两条及其以上的相离的路径，所以双连通分量里的路肯定逃得掉
于是我们只需要考虑双连通分量之外的路，很明显，割边是连接两个连通块之间的路径，肯定是逃不掉的，于是问题就变成了询问两个点，求路径上的割边数，简单的\(e-DCC\)建树之后处理有几条边就行
int num,edcc,dep[N],c[N],head[N],vhead[N],nxt[M],vnxt[M],ver[M],vver[M],tot=1,vtot=1,dfn[N],low[N],bridge[M],n,m,f[N][25],t,ss;
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void add_v(int u,int v){
vnxt[++vtot]=vhead[u],vver[vhead[u]=vtot]=v;
}
void tarjan(int u,int in){
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
bridge[i]=bridge[i^1]=1;
}
}
else if(i!=(in^1))low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u){
c[u]=edcc;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(c[v]||bridge[i])continue;
dfs(v);
}
}
void find_e_dcc(){
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
for(int i=1;i<=n;i++)if(!c[i])++edcc,dfs(i);
for(int i=1;i<=tot;i++)if(bridge[i])add_v(c[ver[i]],c[ver[i^1]]);
}
void init(){
scanf("%d%d",&n,&m);
t=log(n)/log(2.0)+1;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
}
void bfs(int s){
dep[s]=1;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=vhead[u];i;i=vnxt[i]){
int v=vver[i];
if(dep[v])continue;
dep[v]=dep[u]+1;
f[v][0]=u;
for(int i=1;i<=t;i++)f[v][i]=f[f[v][i-1]][i-1];
q.push(v);
}
}
}
int lca(int u,int v){
if(dep[u]>dep[v])swap(u,v);
for(int i=t;i>=0;--i)if(dep[u]<=dep[f[v][i]])v=f[v][i];
if(u==v)return u;
for(int i=t;i>=0;--i)if(f[v][i]!=f[u][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
void prepare(){
init();
find_e_dcc();
bfs(1);
}
int solve(int u,int v){
u=c[u],v=c[v];
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int main(){
prepare();
int q;
scanf("%d",&q);
while(q--){
int u,v;
scanf("%d%d",&u,&v);
ss=0;
int ans=solve(u,v);
printf("%d\n",ans);
}
}
必经点
例题:交通实时查询系统
描述：某城市的交通堵塞问题非常严重，为解决这一问题，该城市建立了实时查询系统来检测所有交通情况。
该城市有 N 个交叉口，M 条道路，每条道路连接两个交叉口，且都是双向的。
实时查询系统的一个重要任务就是帮助司机找到从指定道路行驶到另一条指定道路必经的交叉口有多少个。
就是询问两条边之间的必经点有哪些，很明显也就是两点之间的割点数量
/*
因此求的是两条边之间经过的割点数量
我们只需要缩点之后用lca求两个点双连通分量之间的割点数量即可
由于求的是两条边之间经过的割点数量，因此还需要求出每条边属于的点双连通分量
*/
#define N 20500
#define M 405050
int n,m,s,head[N],vhead[N],ver[M],nxt[M],idx=1,dfn[N],low[N],num,dep[N],fa[N][16],dis[N],stack[N],top,vdcc,root,c[N],id[M],new_id[N],vis[N];
vector<int> dcc[N];
void add(int head[],int a,int b){
ver[++idx]=b,nxt[idx]=head[a],head[a]=idx;
}
void tarjan(int u){
dfn[u]=low[u]=++num;
stack[++top]=u;
if(u==root&&head[u]==0){
dcc[++vdcc].push_back(u);
return;
}
int cnt=0;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
cnt++;
if(root!=u||cnt>1)vis[u]=true;
vdcc++;
int z;
do{
z=stack[top--];
dcc[vdcc].push_back(z);
} while(z!=v);
dcc[vdcc].push_back(u);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void bfs(int s){
queue<int>q;
q.push(s);
dep[s]=1;
dis[s]=(s>vdcc);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=vhead[u];i;i=nxt[i]){
int v=ver[i];
if(dep[v])continue;
dep[v]=dep[u]+1;
dis[v]=dis[u]+(v>vdcc);
fa[v][0]=u;
for(int i=1;i<=15;i++)
fa[v][i]=fa[fa[v][i-1]][i-1];
q.push(v);
}
}
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int k=15;k>=0;k--)if(dep[fa[a][k]] >= dep[b])a=fa[a][k];
if(a==b)return a;
for(int k=15;k>=0;k--)if(fa[a][k]!=fa[b][k])a=fa[a][k],b=fa[b][k];
return fa[a][0];
}
int main(){
while(scanf("%d%d",&n,&m),n || m){
for(int i=1; i <= vdcc; i++) dcc[i].clear();
memset(head,0,sizeof head);
memset(vhead,0,sizeof vhead);
memset(dfn,0,sizeof dfn);
memset(vis,0,sizeof vis);
memset(id,0,sizeof id);
memset(dep,0,sizeof dep);
memset(fa,0,sizeof fa);
num=top=vdcc=0;idx=1;
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(head,a,b),add(head,b,a);
}
for(root=1;root<=n;root++)if(!dfn[root])tarjan(root);
int cnt=vdcc;
for(int i=1;i<=n;i++)
if(vis[i])new_id[i]=++cnt;
for(int i=1;i<=vdcc;i++){
for(int v=0;v<dcc[i].size();v++){
int x=dcc[i][v];
if(vis[x]){
add(vhead,i,new_id[x]);
add(vhead,new_id[x],i);
}
c[x]=i;
}
for(int v=0;v<dcc[i].size();v++){
int x=dcc[i][v];
for(int k=head[x];k;k=nxt[k]){
int y=ver[k];
if(c[y]==i)id[k/2]=i;//处理k/2代表是题目所给的k条边，因为建了反向边导致需要/2
}
}
}
for(int i=1;i<=cnt;i++)
if(!dep[i])
bfs(i);
scanf("%d",&s);
while(s--){
int a,b;
scanf("%d%d",&a,&b);
a=id[a],b=id[b];
int p=lca(a,b);
printf("%d\n",dis[a]+dis[b]-2*dis[p]+(p>vdcc));//若本身就是割点需要加上
}
}
return 0;
}
综合题目
1.network
给定一张 N 个点 M 条边的无向连通图，然后执行 Q 次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量。
先找出\(e-DCC\)，缩点，然后桥的数量就是两个\(e-DCC\)的距离，对于加边操作(若边的两端属于同一个\(e-DCC\)则啥也不做)，我们可以采用标记的形式处理，因为加边之后，那条边的两个端点在原本树上的路径上的所有的边都不再是桥，于是我们在“\(e-DCC\)”树上标记哪些已经因为加边而不是桥了，不断向上跳标记即可，标记的时候记录有多少条边被标记，这就是这次加边导致减少的桥的数量
但这样做时间复杂度较低，我们可以采用并查集优化
不妨思考，若在节点\(u,v\)加边，则原树上\(u-v\)的路径无用，既然无用，但是删除有不方便，我们可以进行压缩
详细说，我们使用并查集，维护每一个节点的上一个没有被标记的边的位置，在每一次修改的时候就可以使用并查集一直向上跳，每一次修改后就把当前节点和当前被标记的那条边的节点的集合合并，这样总体复杂度就降为了log
int head[N],c[N],nxt[N],bridge[M],ver[M],tot=1,edcc,dfn[N],low[N],num,cnt,n,m,fa[N],lst[N];
int vhead[N],vnxt[N],vver[N],vtot=1,dep[N];
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dccadd(int u,int v){
vnxt[++vtot]=vhead[u],vver[vhead[u]=vtot]=v;
}
void tarjan(int u,int in){
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
bridge[i]=bridge[i^1]=1;
}
}
else if((i^1)!=in)low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u){
c[u]=edcc;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(c[v]||bridge[i])continue;
dfs(v);
}
}
void sd(){
tarjan(1,0);
for(int i=1;i<=n;i++)if(!c[i])++edcc,dfs(i);
for(int i=2;i<=tot;i++){
int u=ver[i],v=ver[i^1];
if(c[u]!=c[v])dccadd(c[u],c[v]);
}
}
void bfs(int s){
dep[s]=1;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=vhead[u];i;i=vnxt[i]){
int v=vver[i];
if(dep[v])continue;
lst[v]=u;
dep[v]=dep[u]+1;
q.push(v);
}
}
}
int get(int x) {
return x==fa[x]?x:fa[x] = get(fa[x]);
}
int change(int x, int y) {
int ans=0;
x=get(x),y=get(y);
while(x!=y) {
if(dep[x]<dep[y])swap(x,y);
if(x==1) break;
fa[x]=get(lst[x]);
ans++;
x=get(x);
}
return ans;
}
int main(){
int t=0;
while(~scanf("%d%d",&n,&m)&&(n||m)){
++t;
printf("Case %d:\n",t);
vtot=tot=1;
num=cnt=edcc=0;
memset(head,0,sizeof head);
memset(c,0,sizeof c);
memset(vhead,0,sizeof vhead);
memset(dfn,0,sizeof dfn);
memset(bridge,0,sizeof bridge);
memset(dep,0,sizeof dep);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
sd();
bfs(1);
int ans=edcc-1;
for(int i=1;i<=edcc;i++)fa[i]=i;
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
// puts("AS");
int u,v;
scanf("%d%d",&u,&v);
if(c[u]!=c[v])ans-=change(c[u],c[v]);
printf("%d\n",ans);
}
puts("");
}
}
圆桌骑士
题目描述
国王有时会在圆桌上召开骑士会议。
由于骑士的数量很多，所以每个骑士都前来参与会议的情况非常少见。
通常只会有一部分骑士前来参与会议，而其余的骑士则忙着在全国各地做英勇事迹。
骑士们都争强好胜，好勇斗狠，经常在会议中大打出手，影响会议的正常进行。
现在已知有若干对骑士之间互相憎恨。
为了会议能够顺利的召开，每次开会都必须满足如下要求：
1.相互憎恨的两个骑士不能坐在相邻的两个位置。
2.为了让投票表决议题时都能有结果（不平票），出席会议的骑士数必须是奇数。
3.参与会议的骑士数量不能只有 1 名。
如果前来参加会议的骑士，不能同时满足以上三个要求，会议会被取消。
如果有某个骑士无法出席任何会议，则国王会为了世界和平把他踢出骑士团。
现在给定骑士总数 n，以及 m 对相互憎恨的关系，求至少要踢掉多少个骑士。
分析
我们先建立出原图的补图，也即对每一对没有憎恨关系的骑士连边，根据题意，本题就是要求所有不在奇环上的点，这些点就应该被踢出
引理1：任意一个奇环一定只存在于一个\(v-DCC\)中
根据定义，采用反证法，若有两个节点\(x_1,x_2\)在两个不同的\(v-DCC\)中，并且\(x_1,x_2\)同在一个简单环中，则无论删除环上哪个点，\(x_1,x_2\)同样连通，即两个点的路径中不存在割点，那么因为两个\(v-DCC\)之中也不含有割点，所以无论删除哪个点，\(x_1,x_2\)都是连通的，这意味着\(x_1,x_2\)在同一个\(v-DCC\)中，与\(v-DCC\)的极大性矛盾，假设不成立，原命题成立
引理2：若一个\(v-DCC\)中有两个点被同一个奇环所包含，则整个\(v-DCC\)上的节点都被至少一个奇环所包含
证明：设在\(v-DCC\)的奇环外中任选一个节点\(x\)，并在奇环中任选两个节点\(u,v\)，由于\(v-DCC\)的定义，\(x,u,v\)三点一定在一个简单环上，将环分为三段，分别是\(u-x,v-x，u-v\)，其中\(u-v\)有着另外在奇环上的两条路径，由于奇环的性质，这两条路径所经过的边数奇偶性一定不同，所以与\(u-x-v\)的路径上经过的边数一定可以拼成一个奇数，则\(u,x,v\)三点同在一个奇环上，推广至所有节点即可得上述结论，故命题成立
判定奇环的存在性，可以采用染色法，即我们对于整个\(v-DCC\)中的节点不断染上1,2两种颜色，即若当前节点染1，则其子节点染2，若在染色过程中发现有一个子节点与自己节点的染色相同，则存在奇环。
于是我们最终的做法变成了
- 建图，并求出所有的\(v-DCC\)
- 判断每一个\(v-DCC\)的奇环存在性，若存在则将整个\(v-DCC\)的节点全部标记
- 最后没有被标记的节点就是被踢出的
int tot=1,head[N],nxt[N*N],ver[N*N],dcc,num,dfn[N],low[N],n,m,color[N],op,flag[N],ans,rt,vis[N];
vector<int>edcc[N];
int ljb[N][N];
stack<int>dc;
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void tarjan(int u){
dc.push(u);
dfn[u]=low[u]=++num;
if(u==rt&&head[u]==0){
edcc[++dcc].push_back(u);
return ;
}
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
int z=0;
++dcc;
do{
z=dc.top();dc.pop();
edcc[dcc].push_back(z);
}while(z!=v);
edcc[dcc].push_back(u);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void clear(){
scanf("%d%d",&n,&m);
if(!(n||m))exit(0);
memset(head,0,sizeof head);
memset(vis,0,sizeof vis);
memset(ljb,0,sizeof ljb);
memset(dfn,0,sizeof dfn);
memset(color,0,sizeof color);
num=dcc=ans=0;tot=1;
for(int i=1;i<=n;i++)edcc[i].clear();
while(!dc.empty())dc.pop();
}
void init(){
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
ljb[u][v]=ljb[v][u]=1;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!ljb[i][j]){
add(i,j);
add(j,i);
}
}
}
}
void dfs(int u,int co){
color[u]=co;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(flag[v]){
if(!color[v])dfs(v,3-co);
else if(color[v]==co){
op=-1;
return ;
}
}
}
}
void find(){
for(int i=1;i<=dcc;i++){
int len=edcc[i].size();
for(int j=0;j<len;j++)flag[edcc[i][j]]=1,color[edcc[i][j]]=0;
op=0;
dfs(edcc[i][0],1);
for(int j=0;j<len;j++)flag[edcc[i][j]]=0,vis[edcc[i][j]]+=(op==-1);
}
for(int i=1;i<=n;i++)if(!vis[i])ans++;
}
void solve(){
clear();
init();
for(int i=1;i<=n;i++)if(!dfn[i])rt=i,tarjan(i);
find();
}
int main(){
// freopen("a1.in","r",stdin);
while(1){
solve();
printf("%d\n",ans);
}
}
欧拉路问题
定义：
- 给定一张无向图，若存在一条从\(S\)到\(T\)的路径，使得每条边都不重不漏经过恰好一次，则称这条路径为\(S\)到\(T\)的欧拉路
- 给定一张无向图，若存在一条路径使得从一个节点\(x\)出发不重不漏经过所有的边后又回到了\(x\)，则称这条路为欧拉回路，存在欧拉回路的无向图被称为欧拉图
注:节点可以重复经过
定理： - 一张无向图存在一条欧拉路，当且仅当所有的节点的度数都为偶数且图连通，只有两个节点的度数为奇数，这两个节点就是欧拉路的两端
- 一张无向图为欧拉图，当且仅当图连通且所有节点度数都为偶数
在判定欧拉回路存在后，我们可以借助深度优先遍历和栈求出一种具体的欧拉回路的方案
伪代码如下
因为欧拉图中每个节点的度数为偶数，则经过该节点就一定存在一条未被访问的边可以离开该节点，故在上面的伪代码中调用\(dfs(x)\)，不断递归，最终一定可以递归回\(x\)，产生一条回路
类似于图中，加粗边就是一条回路
需要注意的是，我们并不能够保证这条回路一定经过了所有的节点，于是我们采用了栈，在访问到一些节点的时候，会递归寻找其他回路，我们将所有的回路拼起来就得到了整个欧拉回路，这就是栈在起作用
拼接的方式就是直接嵌入，栈完成了这个嵌入的过程
这个程序的时间复杂度是\(O(nm)\)的，因为一个节点会被重复经历多次，尽管我们知道大部分边已经访问了
一个很简单的优化是，我们采用邻接表存图，将边被标记为已访问的过程可以改为\(head[u]=nxt[i]\)，这样就会使我们不需要重复扫描已经经过的边，提高效率
另外，由于递归层数是\(O(m)\)的，容易爆炸，最好采用非递归的栈实现
int head[100010], ver[1000010], Next[1000010], tot,stack[1000010], ans[1000010]; // 模拟系统栈，答案栈
bool vis[1000010];
int n, m, top, t;
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void euler() {
stack[++top] = 1;
while (top > 0) {
int x = stack[top], i = head[x];
// 找到一条尚未访问的边
while (i && vis[i]) i = Next[i];
// 沿着这条边模拟递归过程，标记该边，并更新表头
if (i) {
stack[++top] = ver[i];
head[x] = Next[i];
vis[i] = vis[i ^ 1] = true;
}
// 与x相连的所有边均已访问，模拟回溯过程，并记录于答案栈中
else {
top--;
ans[++t] = x;
}
}
}
int main() {
cin >> n >> m;
tot = 1;
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
euler();
for (int i = t; i; i--) printf("%d\n", ans[i]);
}