（搬一下本人tarjan blog）
本人写这道题的思路比较恶心：tarjan缩点+拓扑排序+dp
不过学一下拓扑对大家也有好处。
相信大家都是好学的OIer。
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 强连通分量与拓扑排序
拓扑排序
（by 百度百科）
$ \ \ \ \ \ \ $照个人理解，拓扑排序通常是在DAG图中寻找一个适合的解决问题的顺序。
### 如何实现拓扑排序
**方法1：BFS（SPFA优化）**
1、先寻找入度为0的点，把它加入队列。
2、搜寻队列，把队列的点G删去，则如果有点的入度有G点的话，入度- -，当发现又出现入度为0的点时，将该点加入队列。
3、拓扑排序的结果为该队列，在执行删点操作的时候存储在一个数组及可。
**方法2：记忆化搜索**
大多数情况下，并不需要显式的拓扑排序
考虑朴素的回溯算法
若从一个给定的点出发，得到的结果是一样的
因此对于每个点，计算完成后可以把结果保存起来，之后直接返回查表的结果即可
**拓扑排序伪代码(1)：**
```cpp
Topological_sort(G){
统计图G中每个点的入度(可计算重边，但不可计算自环），记为degree[i]
初始化queue和result为空的队列，并将所有degree为0的点加入queue
while (!queue.empty()){
u = queue.pop() // 队首
result.push(u)
for e 是u的出边（若上面计算了重边，这里也要算，与上面一致）
v是e的指向的点
degree[v]--
if (degree[v] == 0) queue.push(v)
}
return result
}
```
**拓扑排序伪代码(2)：**
```cpp
calculate(u){
if (u 已经搜索过) return table[u]
ans = -inf
for (v 是u的出边指向的点)
ans = max(ans, value[u] + calculate(v))
标记u已经搜索过
table[u] = ans
return ans
}
for (i 是G的所有节点)
result = max(result, calculate(i))
print(result)
```
#### ps:源码在我讲完缩点后一起放出来
------------
# 下面重点：
## 强连通分量——缩点（有向有环图）
$ \ \ \ \ \ \ $现在给出一个有向有环图，那么这个图不是一个DAG，所以不能在这种图上做拓扑排序或其他有关DAG的操作了。
如果我们单独把1,2,3点提出来，把它们看做一个团。
我们把这样一个“团点”叫做强连通分量(scc, strong connected component)
通常来讲，一组互相能到达的点叫做连通分量
当这个连通分量不能再大时，便是强连通分量
### 求强连通分量
把有向有环图抽象成一颗DFS树。
那么每一个图上的圈圈就是一个强连通分量。在DFS树中，强连通分量一定长成这样子。
那么问题就被化简成了确定每个强连通分量的根。
### Tarjan
DFS时我们维护两个数组dfn,low
dfn[i]是i点的进入时间
low[i]是从i点出发，所能访问到的最早的进入时间
#### Tarjan-scc伪码
```cpp
DFS(u)
dfn[u] = low[u] = ++timer
stack.push(u)
state[u]=1 //已访问并入栈
for v 是u的一条出边的端点
if (state[v] == 0) //未访问
DFS(v)
low[u] = min(low[u], low[v])
if (state[v] == 1)
low[u] = min(low[u], dfn[v])
if (dfn[u] == low[u])
stack.pop() until 弹出了u //这些点构成一个强连通分量
弹出的点的state[] = 2
Tarjan_scc(G)
timer = 0
for u 是图G的节点
if (state[u] == 0) DFS(u)
```
那怎么找出一个**强连通分量**的所有点
找出scc之后，问题通常会变成两个部分
1、scc内部
2、scc之间
如果把每个scc看成一个点，则是DAG图，即建出一个新图。
#### 新图怎么连边？
记belong[u]为u所在的scc编号
对于每条边u -> v
若belong[u] != belong[v]（就是u，v不在同一个强连通分量）
则给新图加边
belong[u] -> belong[v]（给两个强连通分量连一条边）
------------
# 洛谷【P3387 缩点】
缩点+拓扑排序+DP
#### 为什么要缩点？
```cpp
题目：重复经过的点，权值只计算一次。
```
那么如果是一个环的话，环内所以点的权都肯定被累加，所以我们可以直接把环缩成一个点。
#### 为什么要拓扑排序？~~(其实是作者闲着__疼)~~
```cpp
算法：DAGdp
```
拓扑排序就可以求dp顺序（如果有DAGdp的话，建议加个拓扑）
（对于这道题的dp，拓扑无意义，所以可以跳过拓扑，直接dp）
#### 为什么要dp
因为题目说了啊（逃），其实也很明显啦，对每个点都不断用他的入边的点更新他，取最大值，f[i]表示i点（缩点后）的经过点和最大值。
方程：
```cpp
w代表当前点，rdr数组代表w点的入边的点，dis数组是权值。
f[w]=max(f[w],f[rdr[w][j-1]]+dis_[w]);
```
## 代码
总代码（emm~，码风可能有点丑QAQ）：
```cpp
#include<bits/stdc++.h>
#define maxn 100001
#define maxm 500001
using namespace std;
struct node{
int to,next,from;
}edge[maxm];
queue <int> q;
vector <int> cb[maxn];
vector <int> rdr[maxn];
int ans[maxn],totq,x,y,v,rd[maxn],u,n,m,sum,vis[maxn],dis_[maxn],dis[maxn];
int dfn[maxn],low[maxn],f[maxn],times,cntqq;
int stack_[maxn],heads[maxm],visit[maxn],cnt,tot,index_;
void add(int x,int y) //建边
{
edge[++cntqq].next=heads[x];
edge[cntqq].from=x;
edge[cntqq].to=y;
heads[x]=cntqq;
return;
}
void tuopu() //拓扑排序
{
for(int i=1;i<=tot;i++) //初始化
{
if(rd[i]==0)
q.push(i); //入度为0的都进队列
}
while(!q.empty())
{
int u=q.front();
q.pop();
ans[++totq]=u;
for(int i=1;i<=cb[u].size();i++)
{
v=cb[u][i-1]; //因为vector是从0开始的，所以减1，下面代码的减1也一样
rd[v]--;
if(rd[v]==0)q.push(v);
}
}
}
void tarjan(int x) //tarjan求强连通分量
{
dfn[x]=low[x]=++times;
stack_[++index_]=x; //手写栈嘿嘿嘿
visit[x]=1;
for(int i=heads[x];i!=-1;i=edge[i].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else
if(visit[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
if(low[x]==dfn[x])
{
tot++;//强连通分量编号
while(1)
{
vis[stack_[index_]]=tot; //index_所在的强连通分量编号，等于前面讲的belong
dis_[tot]+=dis[stack_[index_]]; //强连通分量权值累加
visit[stack_[index_]]=0;index_--;
if(x==stack_[index_+1])break;//手写栈嘿嘿嘿
}
}
}
int main(){
memset(heads,-1,sizeof(heads));
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&dis[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); //tarjan
for(int i=1;i<=cntqq;i++){ //拓扑建边
if(vis[edge[i].from]!=vis[edge[i].to])
{
x=vis[edge[i].from];y=vis[edge[i].to];
rd[y]++;cb[x].push_back(y);rdr[y].push_back(x);
}
}
tuopu();
for(int i=1;i<=tot;i++) //dp
{
int w=ans[i];
f[w]=dis_[w];
for(int j=1;j<=rdr[w].size();j++)
f[w]=max(f[w],f[rdr[w][j-1]]+dis_[w]);
}
for(int i=1;i<=tot;i++) //最后统计答案
sum=max(f[i],sum);
printf("%d",sum);
return 0;
}//刚刚好100行
```
# 后记
### 随便给点题
P2341 [HAOI2006]受欢迎的牛
P2002 消息扩散
P1262 间谍网络
# $ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 谢谢观赏，给个赞呗qwq
如果还想学更多知识：请看本人完整[blog](https://www.luogu.org/blog/juruohyfhaha/qiang-lian-tong-fen-liang-yu-ta-pu-pai-xu-lve-xie)