点双：在一个联通块中删去任意一个点后剩下的点仍然能构成联通块，则此联通块叫做点双联通分量。（两个点是一个点双）
性质：任意两点间可构造出两条不相交路径（除起点和终点外不重复经过其他点）。
割点：在一联通块中删去一点可使剩下的点不联通，则此点叫做割点。
一个点可能在多个点双里。
边双：在一个联通块中删去任意一条边后剩下的点仍然能构成联通块，则此联通块叫做边双联通分量。（一个点是一个边双，两个点不是一个边双）
性质：任意两点间可构造出两条不相交路径（不重复经过其他边）。
割边（桥）：在一联通块中删去一边可使剩下的点不联通，则此边叫做割边。
一个点只能在一个边双里。
点双和边双都是对于无向图而言的。
强联通分量：任意两个点可以两两到达的图是强联通的。
强联通分量不存在交点。
对于每个强联通分量进行缩点后会形成一张 DAG。
强联通分量是对于有向图而言的。
搜索树
从一个点开始进行 DFS，最终得到一棵生成树，这棵树叫搜索树。在该搜索树上的边叫树边。
返祖边：原图中节点连向搜索树中祖先节点的边。
tarjan 求强联通分量（B3609）
#include<bits/stdc++.h>
using namespace std;
const int N=11451,M=114514;
struct node{
int to,next;
}e[M];
int h[N],cnt;
int n,m;
int dfn[N],low[N],tot,ans;
//dfn dfs序 low 子树能追溯最早的栈中节点
int f[N];//属于哪个强联通分量
int st[N],len;
bool vis[N],flag[N];
vector<int> ansv[N];
void Link(int u,int v){
e[++cnt].to=v;
e[cnt].next=h[u];
h[u]=cnt;
}
void tarjan(int x){
dfn[x]=low[x]=++tot;
st[++len]=x;
vis[x]=true;
for(int i=h[x],y;i;i=e[i].next){
y=e[i].to;
if(!dfn[y]){//未被访问过
tarjan(y);//dfs
low[x]=min(low[x],low[y]);//用子节点的low更新
}else if(vis[y]){//被访问过且在栈中（返祖）
low[x]=min(low[x],dfn[y]);//用其dfs序更新
}//否则就是访问过但已出栈，这是已操作完的节点，无需访问
}
if(dfn[x]==low[x]){//是所在的强联通分量中根
ans++;//其间所有节点构成该强联通分量
ansv[ans].push_back(x);
while(st[len]!=x){
ansv[ans].push_back(st[len]);//退栈
vis[st[len]]=false;
f[st[len]]=ans;
len--;
}
vis[x]=false;
f[x]=ans;
len--;
}
}
int main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
Link(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);//确保没有没被访问的节点
for(int i=1;i<=ans;i++)
sort(ansv[i].begin(),ansv[i].end());
cout<<ans<<endl;//输出答案
for(int i=1;i<=n;i++){
if(!flag[f[i]]){
flag[f[i]]=true;
for(int j=0;j<ansv[f[i]].size();j++)
cout<<ansv[f[i]][j]<<' ';
cout<<endl;
}
}
return 0;
}
例题：P3387 【模板】缩点
思路：将强联通分量进行缩点操作，因为强联通分量中各点之间相互可达，所以可以合并权值。缩点后原图变为 DAG，可以通过拓扑排序求最大和。
#include<bits/stdc++.h>
using namespace std;
const int N=11451,M=114514;
struct node{
int to,next;
}e[M];
int h[N],cnt;
int n,m,a[N];
int dfn[N],low[N],tot;
int f[N],w[N],s;
//f 所属联强联通分量 w 强联通分量权值 s 个数
int st[N],len;
int in[N],pre[N],ans;//pre 前置节点中最大权值
bool vis[N];
vector<int> v[N];
void Link(int x,int y){
e[++cnt].to=y;
e[cnt].next=h[x];
h[x]=cnt;
}
void tarjan(int x){//缩点
dfn[x]=low[x]=++tot;
st[++len]=x;
vis[x]=true;
for(int i=h[x],y;i;i=e[i].next){
y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}else if(vis[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
s++;
f[x]=s;//加入强联通分量
w[s]+=a[x];//合并权值
vis[x]=false;
while(st[len]!=x){
f[st[len]]=s;
w[s]+=a[st[len]];
vis[st[len]]=false;
len--;
}
len--;
}
}
void topsort(){//拓扑排序
queue<int> q;
for(int i=1;i<=s;i++)
if(!in[i])q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
ans=max(ans,w[x]+=pre[x]);//更新答案 前面来的+此强联通分量的
for(int i=0,y;i<v[x].size();i++){
y=v[x][i];
pre[y]=max(pre[y],w[x]);//更新 pre
in[y]--;
if(!in[y])q.push(y);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
Link(x,y);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int x=1;x<=n;x++){
for(int i=h[x],y;i;i=e[i].next){
y=e[i].to;
if(f[x]!=f[y]){//注意是缩完后的点之间连边
v[f[x]].push_back(f[y]);//here
in[f[y]]++;//here
}
}
}
topsort();
cout<<ans;
return 0;
}