ps.有关Tarjan算法缩点的简要回顾。
今天上午在Luogu随机到了这道题 Luogu P3420，题目大概是这样：
题目描述
Byteazar the Dragon拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助Byteazar去决策最少要破坏多少存钱罐。
你需要写一段程序包括：读入存钱罐的数量以及相应的钥匙的位置，求出能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量并将其输出。
输入输出格式
输入格式：
第一行：包括一个整数N（1<=N<=1000000)，这是Byteazar the Dragon拥有的存钱罐的数量。
存钱罐（包括它们对应的钥匙）从1到N编号。
接下来有N行：第i+1行包括一个整数x，表示第i个存钱罐对应的钥匙放置在了第x个存钱罐中。
输出格式：
仅一行：包括一个整数，表示能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量。
输入输出样例
4
2
1
2
4
2
看到这道题的时候我是很高兴的：这不就是记录一个入度的问题嘛！图都不需要建就做好了。于是写了一个前后不超20行的代码就交了，果断拿了20分。
然后我开始重新审视这道题目：我发现题目是有环的，而且还可能有好多个，所以入度为零的点可能一个都没有，而且还有各种问题……
糟了，难度一下就上来了。不过好在我会复制敲Tarjan的板子！可以发现，只要砸开（打开）一个环里的任一个存钱罐，那么整个环就都会被打开。
缩点！
Tarjan的本质其实就是Dfs的过程，而缩点的思想是，我们将未搜过的点称为白点，已退栈（已经Dfs过）的点称为黑点，而正在Dfs栈中的点定义为灰点。
然后我们可以愉快地Dfs，遇到白点就走，黑点就返回（因为已经搜完了）。
但是如果搜着搜着搜到了灰点，也就是vis[x] = 1，dfn[x] < dfn[now]的点，那么说明这玩意儿转回去了……那这就是一个环。
这时我们对每个节点维护的2个变量——dfn（被dfs到的次序，也叫时间戳），low（标记了节点i能够回溯到的最早位于栈中的节点，也就是你走回去到达的节点啦）其中的low进行操作取min，这里具体的原理和作用我并说不很清楚，背过理解就好。
之后就弹栈，将这一段环染成同一种颜色，也就是缩点。
int stack[maxn], top;
void Tarjan(int s) {
dfn[s] = low[s] = ++dfn_num;
vis[s] = , stack[++top] = s;
for(int i=head[s]; i; i=edge[i].nxt) {
int v = edge[i].v;
if( !dfn[v] ) {
Tarjan(v), low[s] = min(low[s], low[v]);
} else if( vis[v] ) low[s] = min(low[s], dfn[v]);
}
if( dfn[s]==low[s] ) {
vis[s] = , col[s] = ++col_num;
while( stack[top]!=s ) {
col[stack[top]] = col_num;
vis[stack[top]] = , --top;
}
--top;
}
}
Tarjan缩点
不一会我就复制来了敲完了板子，高高兴兴的提交了上去——40分。
？？？
其实这篇博客的重点已经写完了，不过我还要继续写。
我只好仔细对着题解检查然后调试，发现我边建反了……
而且Tarjan判断一个点已经被搜过的根据是dfn[] != 0，不是vis[]，vis[]只是一个是否在栈中的标记，也就是给灰点的标记……而我在main()里却拿vis[]来判断是否搜过这个点了。
以及在对新图做什么的时候，注意此时的点已经不是一开始的点了，而是一个颜色代表一个点。所以操作的时候大多是应该是对col[n]操作，而不是n……
然后再统计一下入度为0的点就好啦。
最后帖一波代码。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int n, t, head[maxn], vis[maxn], degree[maxn], ans;
int dfn[maxn], low[maxn], col[maxn], dfn_num, col_num; struct Edge { int v, nxt; }edge[maxn]; inline void read(int &x) {
register char ch = ; x = ;
while( !isdigit(ch) ) ch = getchar();
while( isdigit(ch) ) x = (x*) + (ch^), ch = getchar();
} int stack[maxn], top; void Tarjan(int s) {
dfn[s] = low[s] = ++dfn_num;
vis[s] = , stack[++top] = s;
for(int i=head[s]; i; i=edge[i].nxt) {
int v = edge[i].v;
if( !dfn[v] ) {
Tarjan(v), low[s] = min(low[s], low[v]);
} else if( vis[v] ) low[s] = min(low[s], dfn[v]);
}
if( dfn[s]==low[s] ) {
vis[s] = , col[s] = ++col_num;
while( stack[top]!=s ) {
col[stack[top]] = col_num;
vis[stack[top]] = , --top;
}
--top;
}
} int main(int argc, char const *argv[])
{
scanf("%d", &n);
for(int i=; i<=n; ++i) {
read(t), edge[i].v = i;
edge[i].nxt = head[t], head[t] = i;
}
for(int i=; i<=n; ++i) if( !col[i] ) Tarjan(i);
for(int i=; i<=n; ++i) {
for(int j=head[i]; j; j=edge[j].nxt)
if( col[edge[j].v]!=col[i] ) ++degree[col[edge[j].v]];
}
for(int i=; i<=col_num; ++i) if( !degree[i] ) ++ans;
printf("%d\n", ans);
return ;
}