$Tarjan$是图论中求解关于图的连通性的相关问题的算法，$Tarjan$基于深搜$dfs$实现。
利用两个关键数组：$dfn[],low[]$。
$dfn[i]:$结点$i$的时间戳。
$low[i]:$结点$i$所能遍历的所有结点的最小$dfn$，可以类比并查集的$fa[i]$理解。
$id:$当前时间。
每次我们从一个结点$u$开始搜索，我们结点$u$能遍历到的所有结点组成的树成为结点$u$的搜索树，同时我们利用栈来保存处于同一个强连通分量的结点。
算法的流程：
1.每次搜索到一个结点$u$，先初始化$dfn[u]=low[u]=++id$，然后结点$u$入栈。
2.然后依次遍历结点$u$的子树$v$，如果该点没有搜索过即$(!dfn[v])$就$dfs(v)$，然后更新$low[u]=min(low[u],low[v])$。
3.如果结点$v$搜索过且在栈中，说明该节点$v$可能是潜在的连通块的根，更新$low[u]=min(low[u],dfn[v])$，这里使用$dfn[v]$，因为$v$有可能属于别的连通块了。
4.搜索完$u$的所有能遍历的结点后，判断$dfn[u]=low[u]$，如果相等说明$u$是强连通分量的一个根，此时属于这个强连通分量的所有结点的$low[v]=low[u]$，然后回溯栈中所有节点染色为同一个连通块，同时可以统计该连通块的个数。
时间复杂度：$O(E+V)$
$Tarjan$能解决的一些问题：
1.判断图是否连通。
2.判断图的连通分量个数。
3.判断每个连通分量的结点数。
4.缩点，将有向有环图(无向有环图的一条边可等价为两个有向边)转换为有向无环图$(DAG)$
5.找到所有缩点，缩边。
6.求删去一个结点后图的连通分量个数，即判断每个点的缩边个数。
7.缩点后建立$DAG$，实现拓扑排序，树形$dp$，点权和状态转移等操作。
8.求缩点后新图的点出度，入度情况。
$\dots\dots$
模板：
int n,m,dfn[N],low[N],id,vis[N],ans,col[N],num[N],sum=0;
vector<int>e[N]; //dfs[i]记录结点i遍历顺序,low[i]记录结点i及其子结点最小遍历顺序,vis[i]标记是否在栈中。
stack<int>s; //col[i]记录结点i属于那个连通块(本题没用),num[i]记录第i个连通块的结点数.
void dfs(int u){
dfn[u]=low[u]=++id;//记录dfs顺序
s.push(u);//入栈
vis[u]=1;//标记入栈.
for(auto v:e[u]){
if(!dfn[v]){
dfs(v); //没有遍历的点进行遍历然后更新low
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);//如果已经遍历过而且在栈中 则取low较小值(这里是潜在的连通块)
}
if(dfn[u]==low[u]){ //该点是连通块的"根" 注意孤立点也是连通块.
vis[u]=0; //回溯标记，并染色.
col[u]=++sum;
num[sum]++;
while(s.top()!=u){ //依次出栈.
col[s.top()]=sum;
vis[s.top()]=0;
s.pop();
num[sum]++;
}
s.pop();
}
}求割点，只需要判断$low[v]\ge dfn[u]$即可，因为如果满足的话，显然去掉$u$后就不能访问$v$子树了，所以$u$就是割点，$edge(u,v)$就是割边。
void dfs(int u,int fa){
dfn[u]=low[u]=++id;
for(int i=h[u];i;i=e[i].nt){
int v=e[i].to;
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) cut[u]++; //关键
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
}1.POJ 2117
无向图删去后一个点后的最多连通分量数。
思路：以$i$为根依次进行搜索，记录该点的割边数$cut[i]$，如果$cut[i]=0$，说明它是孤立点，删去它后贡献减1，如果$cut[i]=1$且它只有一个儿子，删去它后，连通分量个数还是$1$，贡献也是$cut[i]-1$，若$cut[i]>1$，且$i$为根，则新增的连通分量数$cut[i]-1$，因为不包括自身的连通分量。
void dfs(int u,int fa){
dfn[u]=low[u]=++id;
for(int i=h[u];i;i=e[i].nt){
int v=e[i].to;
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) cut[u]++;
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);add(u,v);
}
int tot=0,mx=-1;
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs(i,-1),tot++,cut[i]--;
}
}
for(int i=1;i<=n;i++) printf("%d ",tot+cut[i]);2. 2020ICPC网络赛 D.Router Mesh
题意：给定无向图，求删去每个结点后的连通分量数。
思路：利用上题的方法求出$cut[i]$，然后用原连通分量数$tot+cut[i]$即可。
3.POJ 2553
题意：求有向图缩点后连通分量没有出度的点。
思路：$tarjan$缩点给连通块染色，然后判断每条边$edge(u,v)$的$bl[u]$是否等于$bl[v]$，如果不相等说明结点$bl[u]$这个连通分量有出度，最后输出$bl[u]=0$的点即可。
void dfs(int u){
dfn[u]=low[u]=++id;
vis[u]=1,s.push(u);
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
bl[u]=++tot,vis[u]=0;
while(s.top()!=u){
vis[s.top()]=0,bl[s.top()]=tot,s.pop();
}
s.pop();
}
}
for(int u=1;u<=n;u++)
for(int j=0;j<e[u].size();j++){
if(bl[u]!=bl[e[u][j]]){
chu[bl[u]]=true;break;
}
}
for(int i=1;i<=n;i++)
if(!chu[bl[i]]) printf("%d ",i);4.10103. 「一本通 3.6 练习 4」电力
跟$POJ2117$ 一样的，不写了。
5.P3388
求无向图的割点。
注意：结点为根且儿子只有一个不是割点。
void dfs(int u,int fa){
dfn[u]=low[u]=++id;
//s.push(u);
int son=0;
for(int i=h[u];i;i=e[i].nt){
int v=e[i].to;
if(!dfn[v]){
son++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) cut[u]=1;
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
if(fa<0&&son==1) cut[u]=0; //结点u为树根 且只有一个儿子
}6.P2863 [USACO06JAN]The Cow Prom S
直接一遍搜然后统计$cnt$即可。
void dfs(int u,int fa){
dfn[u]=low[u]=++id;
vis[u]=1,s.push(u);
for(int v:e[u]){
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){ //统计cnt>1 即为结点个数大于1的强连通分量
int cnt=1;
vis[u]=0;
while(s.top()!=u){
cnt++,vis[s.top()]=0,s.pop();
}
s.pop();
if(cnt>1) ans++;
}
}7.P3387 【模板】缩点
思路：缩点转$DAG$图跑$dp$或者拓扑即可。
$dp$写法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m,id,cnt;
int a[N],dfn[N],low[N],vis[N],bl[N],b[N];
vector<int>e[N],ne[N];
stack<int>s;
void dfs(int u,int fa){
dfn[u]=low[u]=++id;
vis[u]=1,s.push(u);
for(int v:e[u]){
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
bl[u]=++cnt,b[cnt]+=a[u];
vis[u]=0;
while(s.top()!=u){
vis[s.top()]=0,bl[s.top()]=cnt,b[cnt]+=a[s.top()],s.pop();
}
s.pop();
}
}
int f[N];
void fun(int u){
if(f[u]) return;
f[u]+=b[u];int mx=0;
for(int v:ne[u]){
if(!f[v]) fun(v);
mx=max(mx,f[v]);
}
f[u]+=mx;
}
int main(){
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v),e[u].pb(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) dfs(i,-1);
}
for(int u=1;u<=n;u++){
for(int v:e[u]){
if(bl[u]!=bl[v]){
ne[bl[u]].pb(bl[v]);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!f[i]){
fun(i);
ans=max(ans,f[i]);
}
}
printf("%d\n",ans);
return 0;
}拓扑写法：
int topo(){
queue<int>q;
for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i),f[i]=b[i];
while(!q.empty()){
int u=q.front();q.pop();
for(int v:ne[u]){
in[v]--;
f[v]=max(f[v],f[u]+b[v]);
if(!in[v]) q.push(v);
}
}
int ans=0;
for(int i=1;i<=cnt;i++) ans=max(ans,f[i]);
return ans;
}8. P2341 HAOI2006 受欢迎的牛 G
思路：有向图先缩点，然后判断每个点出度是否为0，如果出现一个以上的点出度为0，说明不可能有能被所有其他点遍历的点，否则那个一点肯定是能被其他点遍历到的点，因为其他点一直有出度可以出去，直到找到那个点就停止。
for(int u=1;u<=n;u++){
for(int v:e[u]){
if(bl[u]!=bl[v]){
out[bl[u]]++;
}
}
}
int f=0;
for(int i=1;i<=cnt;i++){
if(!f&&!out[i]){
f=i;
}
else if(!out[i]){
return printf("0\n"),0;
}
}9.P2746 [USACO5.3]校园网Network of Schools
思路：任务$A$答案就是入度为$0$的点，因为这些点不能由其他点分发过来，
任务$B$就是取入度为0点的个数和出度为0的点个数的最大值，但是需要注意的是如果图本身是一个环的话就不需要再扩展了。
for(int u=1;u<=n;u++){
for(int v:e[u]){
if(bl[u]!=bl[v]){
in[bl[v]]++,out[bl[u]]++;
}
}
}
int tot=0,tmp=0;
for(int i=1;i<=cnt;i++){
if(!in[i]) tot++;
if(!out[i]) tmp++;
}
printf("%d\n",tot);
if(cnt==1) printf("0\n");
else printf("%d\n",max(tot,tmp));
