拓扑排序复习&强连通分量学习笔记
chinaxjh
2019-11-10 19:44:15
# 强连通分量
# Part 1
## 前言
强连通分量常常用来缩点，使原有向图变成$DAG$，搭配拓扑排序使用
# Part 2
## 模板
#### $Tarjan$
$dfn[i]$：就是一个时间戳（被搜到的次序），一旦某个点被DFS到后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以常根据$dfn$的值来判断是否需要进行进一步的深搜。
$low[i]$：该子树中，且仍在栈中的最小时间戳，像是确立了一个关系，$low[i]$相等的点在同一强连通分量中。
注意初始化时 $dfn[i] = low[i] = ++cnt.$
```cpp
void tarjan(int x)
{
dfn[x]=++num;
low[x]=num;
v[x]=true;
stacks[++top]=x;
int i;
for (i=las[x];i;i=nxt[i])
{
int y;
y=a[i];
if (!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
} else if (v[y]) low[x]=min(low[x],dfn[y]);
}
if (low[x]==dfn[x])
{
int k;
color_num++;
while (stacks[top]!=x)
{
k=stacks[top];
v[k]=false;
color[k]=color_num;
top--;
}
k=stacks[top];
v[k]=false;
color[k]=color_num;
top--;
}
}
```
# Part 3
## 例题
#### 校园网Network of Schools
[题目](https://www.luogu.org/problem/P2746)
$Tarjan+$出入度判断瞎搞
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=30005;
int dfn[N],low[N],v[N],stacks[N],las[N],nxt[N],a[N],color[N],ru[N],chu[N];
int num,top,color_num,n,i,x,len,ans1,ans2,j;
void add(int x,int y)
{
len++;
a[len]=y;
nxt[len]=las[x];
las[x]=len;
}
void tarjan(int x)
{
dfn[x]=++num;
low[x]=num;
v[x]=true;
stacks[++top]=x;
int i;
for (i=las[x];i;i=nxt[i])
{
int y;
y=a[i];
if (!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
} else if (v[y]) low[x]=min(low[x],dfn[y]);
}
if (low[x]==dfn[x])
{
int k;
color_num++;
while (stacks[top]!=x)
{
k=stacks[top];
v[k]=false;
color[k]=color_num;
top--;
}
k=stacks[top];
v[k]=false;
color[k]=color_num;
top--;
}
}
int main()
{
cin>>n;
for (i=1;i<=n;i++)
{
while (1)
{
scanf("%d",&x);
if (x==0) break;
add(i,x);
}
}
for (i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
for (i=1;i<=n;i++)
for (j=las[i];j;j=nxt[j])
if (color[i]!=color[a[j]])
{
chu[color[i]]++;
ru[color[a[j]]]++;
}
for (i=1;i<=color_num;i++)
{
if (!ru[i]) ans1++;
if (!chu[i]) ans2++;
}
cout<<ans1<<endl;
if (color_num==1) cout<<0<<endl;
else cout<<max(ans1,ans2)<<endl;
}
```