割点和割边
在无向图中，
割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。
割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。
割点与割边的关系
1.有割点不一定有割边，有割边一定有割点。
2.割边的两个端点中一定有一个是割点。
判断割点
若顶点 \(u\) 的所有儿子节点可以不通过 \(u\) 而访问到 \(u\) 的祖先节点，则去掉 \(u\) 后不会影响连通性，即 \(u\) 不是割点。
反之，若顶点 \(u\) 的至少一个儿子节点必须通过 \(u\) 才能访问到 \(u\) 的祖先节点，则去掉 \(u\) 后，这些儿子节点就不能访问到 \(u\) 的祖先节点了，影响了连通性，即 \(u\) 是割点。
但是， \(dfs\) 的出发点没有祖先节点，用以上的方法还无法判断。
若它只有一棵子树，它就不是割点。
反之，去掉它后它的子树不能互相连通，它就是割点。
具体实现
定义一个 \(\operatorname{low}\) 数组， \(\operatorname{low}_x\) 表示节点 \(x\) 不通过父亲节点所能访问到的祖先节点中 \(\operatorname{dfn}\) 序的最小值。
若节点 \(u\) 可以访问到节点 \(v\) ，那么在 \(v\) 回溯到 \(u\) 时，若 \(\operatorname{dfn}_v<\operatorname{low}_u\) ，则 \(\operatorname{low}_u=\operatorname{dfn}_v\) 。
因为祖先节点的 \(\operatorname{dfn}\) 序一定比自身小，所以若一个点 \(u\) 的任一子节点 \(v\) 都满足 \(\operatorname{low}_v<\operatorname{dfn}_u\) ，则 \(u\) 不是割点。
反之，若至少有一个子节点 \(v\) 满足 \(\operatorname{low}_v \geq \operatorname{dfn}_u\) ，则去掉 \(u\) 后会影响连通性，则 \(u\) 是割点。
对于两个点 \(u,v\) ，若 \(\operatorname{low}_v>\operatorname{dfn}_u\) ，则说明 \(u-v\) 是割边。
因为去掉这条边后， \(v\) 不能访问到 \(u\) 的祖先节点，会影响连通性。
割点板子
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e4+10;
int n,m,dfn[N],low[N],cnt,sum;
vector <int> e[N];
bool flag[N];
int min_(int x,int y)
{
return x<y?x:y;
}
void tarjan(int x,int fa)
{
int son=0;
dfn[x]=low[x]=++cnt;
for(int i=0;i<e[x].size();i++)
{
if(!dfn[e[x][i]])
{
tarjan(e[x][i],x);
low[x]=min_(low[x],low[e[x][i]]);
if(low[e[x][i]]>=dfn[x]&&x!=fa) flag[x]=true;
if(x==fa) son++;
}
low[x]=min_(dfn[e[x][i]],low[x]);
}
if(son>=2) flag[x]=true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,i);
for(int i=1;i<=n;i++) sum+=flag[i];
printf("%d\n",sum);
for(int i=1;i<=n;i++)
if(flag[i]) printf("%d ",i);
return 0;
}
johnson
用于求全源最短路。
先建一个新点 0 ，向每个点都连一条边权为 0 的边。
从 0 开始跑一遍 SPFA ，顺便把负环判了。
记 \(d_x\) 为 0 到 \(x\) 的最短路长度，记 \(w(u,v)\) 为 \((u,v)\) 这条边的边权。
接下来，重新赋一遍边权： \(w'(u,v)=w(u,v)+d_u-d_v\) .
可以证明，这样赋边权一定非负。
在新图上跑 \(n\) 边 dijkstra 即可。注意最后的答案要减去前面赋边权时加上的值。
板子
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=3010;
const int inf=1e9;
int n,m,dis[N];
int d[N],vis[N],cnt[N];
struct node
{
int to,val;
};
struct F
{
int x,d;
};
bool operator < (F x,F y)
{
return x.d>y.d;
}
vector <node> e[N];
queue <int> q;
priority_queue <F> Q;
void add(int x,int y,int z)
{
e[x].push_back((node){y,z});
}
bool SPFA(int s)
{
for(int i=0;i<=n;i++) d[i]=inf;
for(int i=0;i<=n;i++) vis[i]=0;
for(int i=0;i<=n;i++) cnt[i]=0;
vis[s]=1,d[s]=0,q.push(s);
while(q.size())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=0;i<e[x].size();i++)
{
int nto=e[x][i].to;
int nval=e[x][i].val;
if(d[nto]>d[x]+nval)
{
d[nto]=d[x]+nval;
cnt[nto]=cnt[x]+1;
if(cnt[nto]>n) return true;
if(!vis[nto]) vis[nto]=1,q.push(nto);
}
}
}
return false;
}
void dij(int s)
{
for(int i=1;i<=n;i++) dis[i]=inf;
for(int i=1;i<=n;i++) vis[i]=0;
dis[s]=0,vis[s]=1,Q.push((F){s,0});
while(Q.size())
{
F x=Q.top();Q.pop();vis[x.x]=0;
for(int i=0;i<e[x.x].size();i++)
{
int nto=e[x.x][i].to;
int nval=e[x.x][i].val;
if(dis[nto]>dis[x.x]+nval)
{
dis[nto]=dis[x.x]+nval;
if(!vis[nto]) vis[nto]=1,Q.push((F){nto,dis[nto]});
}
}
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
}
for(int i=1;i<=n;i++) add(0,i,0);
if(SPFA(0)) puts("-1"),exit(0);
e[0].clear();
for(int i=1;i<=n;i++)
for(int j=0;j<e[i].size();j++)
e[i][j].val+=d[i]-d[e[i][j].to];
for(int i=1;i<=n;i++)
{
dij(i);
int ans=0;
for(int j=1;j<=n;j++)
{
if(dis[j]==inf) ans+=j*inf;
else ans+=j*(dis[j]-d[i]+d[j]);
}
printf("%lld\n",ans);
}
return 0;
}
强联通分量
设 \(\text{dfn}_x\) 表示 \(x\) 在 dfs 时被访问到的次序（即时间戳），
设 \(\text{low}_x\) 表示 \(x\) 所能访问到的最小的 \(\text{dfn}\) 值。
首先，开一个栈，存现在正在处理的节点。
下面，设 \(x\) 为当前在搜的父亲节点， \(y\) 为当前在搜的儿子节点，有几种情况：
1.\(y\) 没有被访问过：搜下去。回溯时， \(\text{low}_x=\min(\text{low}_x,\text{low}_y)\) 。
2.\(y\) 被访问过，但还在栈中，即还没有处理完： \(\text{low}_x=\min(\text{low}_x,\text{dfn}_y)\) 。
3.\(y\) 已经被处理完了：不做操作。
接下来，考虑何时会出现一个新的强联通分量。
发现对于一个强联通分量，有且仅有一个点的 \(\text{dfn}_x=\text{low}_x\) ，这个点即为这个强联通分量中被最先访问到的点。所以，当找到这样的点时，就把栈中存着的点不断弹出，直到把 \(x\) 弹出。这些点就构成了一个强联通分量。
板子
求最大联通分量。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+10;
int n,m,mx;
int dfn[N],low[N],cnt;
int tot,sz[N],scc[N];
int st[N],vis[N],top;
vector <int> e[N];
int MIN(int x,int y)
{
return x<y?x:y;
}
void tarjan(int x)
{
dfn[x]=++cnt,low[x]=dfn[x];
st[++top]=x,vis[x]=1;
for(int i=0;i<e[x].size();i++)
{
if(!dfn[e[x][i]])
{
tarjan(e[x][i]);
low[x]=MIN(low[x],low[e[x][i]]);
}
else if(vis[e[x][i]])
low[x]=MIN(low[x],dfn[e[x][i]]);
}
if(dfn[x]==low[x])
{
tot++;
while(st[top]!=x)
{
scc[st[top]]=tot,sz[tot]++;
vis[st[top]]=0,top--;
}
scc[x]=tot,sz[tot]++;
vis[x]=0,top--;
if(sz[tot]>sz[mx]) mx=tot;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,tp;
scanf("%d%d%d",&x,&y,&tp);
e[x].push_back(y);
if(tp==2) e[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
printf("%d\n",sz[mx]);
for(int i=1;i<=n;i++)
if(scc[i]==mx) printf("%d ",i);
return 0;
}
2-SAT
问题描述
把每个变量拆成 \(true\) 点和 \(false\) 点。
连边：
以 \(x\&y=false\) 为例。
可以发现，
若 \(x=false\) ，没有明确关系，不连边。
若 \(x=true\) ，则 \(y=false\) ，故连一条从 \(x\) 的 \(true\) 点到 \(y\) 的 \(false\) 点的边。
以此类推。
判断是否有解：只要同一个变量的 \(true\) 点和 \(false\) 点不在同一个强联通分量内则有解。
赋值：可以发现，一个变量拆出的两个点一定是有相互推倒的关系的，所以把变量的值赋为 \(true\) 点和 \(false\) 点中拓扑序较大的那个即可。
代码实现
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e6+10;
int n,m;
int dfn[N],low[N],cnt;
int tot,sz[N],scc[N];
int st[N],vis[N],top;
vector <int> e[N];
int MIN(int x,int y)
{
return x<y?x:y;
}
void add(int x,int y)
{
e[x].push_back(y);
}
void tarjan(int x)
{
dfn[x]=++cnt,low[x]=dfn[x];
st[++top]=x,vis[x]=1;
for(int i=0;i<e[x].size();i++)
{
if(!dfn[e[x][i]])
{
tarjan(e[x][i]);
low[x]=MIN(low[x],low[e[x][i]]);
}
else if(vis[e[x][i]])
low[x]=MIN(low[x],dfn[e[x][i]]);
}
if(dfn[x]==low[x])
{
tot++;
while(st[top]!=x)
{
scc[st[top]]=tot,sz[tot]++;
vis[st[top]]=0,top--;
}
scc[x]=tot,sz[tot]++;
vis[x]=0,top--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,x,y;
scanf("%d%d%d%d",&a,&x,&b,&y);
if(x==0&&y==0) add(a+n,b),add(b+n,a);
if(x==0&&y==1) add(a+n,b+n),add(b,a);
if(x==1&&y==0) add(a,b),add(b+n,a+n);
if(x==1&&y==1) add(a,b+n),add(b,a+n);
}
for(int i=1;i<=2*n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
if(scc[i]==scc[i+n]) puts("IMPOSSIBLE"),exit(0);
puts("POSSIBLE");
for(int i=1;i<=n;i++)
printf("%d ",(int)(scc[i]>scc[i+n]));
return 0;
}
差分约束
可以用于解每个方程都是 \(x_i \leq x_j + w\) 形式的方程组。
首先，若方程为 \(x_i \geq x_j+w\) 或 \(x_i=x_j+w\) 都可以通过一些变形得到上面形式的方程。
发现这样形式的方程与最短路里 \(dis_i \leq dis_j+w\) 是类似的，所以可以建出图，用最短路求解。
建一个新点 0 ，向每个点都连一条边权为 0 的边，从 0 开始跑一遍最短路即可。
但是，图里可能会有负环，要用 SPFA 判掉，若有负环则说明方程组无解。
板子
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=5010;
const int inf=1e18;
int n,m;
int dis[N],vis[N],cnt[N];
struct node
{
int to,val;
};
vector <node> e[N];
queue <int> q;
void add(int x,int y,int z)
{
e[x].push_back((node){y,z});
}
bool SPFA(int s)
{
for(int i=0;i<=n;i++) dis[i]=inf;
for(int i=0;i<=n;i++) vis[i]=0;
for(int i=0;i<=n;i++) cnt[i]=0;
vis[s]=1,dis[s]=0,q.push(s);
while(q.size())
{
int x=q.front();vis[x]=0,q.pop();
for(int i=0;i<e[x].size();i++)
{
int t=e[x][i].to,v=e[x][i].val;
if(dis[t]>dis[x]+v)
{
cnt[t]=cnt[x]+1,dis[t]=dis[x]+v;
if(cnt[t]>=n+1) return true;
if(!vis[t]) q.push(t),vis[t]=1;
}
}
}
return false;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(y,x,z);
}
for(int i=1;i<=n;i++) add(0,i,0);
if(SPFA(0)) puts("NO"),exit(0);
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
return 0;
}