主要算法
强连通分量Tarjan
强连通分量的缩点
P1：Tarjan基础
题目描述
问题描述
给定一张n个点，m条边组成的有向图，对于每个节点u，输出每个节点的dfn和low。
定义： dfn为节点u搜索的次序编号。
low为u或u的子树能够追溯到的最早的栈中节点的次序号。
加入in数组表示是否在栈内，同时考虑返祖边用dfn进行更新的情况。
输入
第一行n和m。
接下来m行u和v，表示u到v的边。
输出
n行，每行两个整数，分别表示dfn和low。
样例输入
3 3
1 2
2 1
2 3样例输出
1 1
2 1
3 3数据范围
n<=10000
题解报告
题目大意
给定一个有向图，要求使用Tarjan算法求出每个节点的深度优先数（dfn）和能追溯的最早祖先的dfn值（low），并按节点顺序输出这两个值。
解题思路
Tarjan算法的核心思想是通过深度优先搜索（DFS）遍历图中的所有节点，利用栈来跟踪当前搜索路径上的节点，并通过维护两个关键数组dfn和low来识别强连通分量（SCC）：
dfn数组：记录每个节点被访问的时间戳（即DFS的访问顺序）。
low数组：记录当前节点或其子树能追溯到的最早栈中节点的dfn值。
具体步骤
初始化：对每个未被访问的节点启动DFS。初始化dfn和low为当前时间戳，并将节点压入栈。
遍历邻接点：对于当前节点的每个邻接点：
若邻接点未被访问，递归处理该邻接点，并用其low值更新当前节点的low值。
若邻接点已被访问且在栈中（属于当前路径），则用其dfn值更新当前节点的low值。
回溯处理：当DFS回溯到某个节点且其dfn等于low时，该节点为当前SCC的根，将栈中节点弹出直到当前节点，形成一个SCC。
Tips
题解报告按照标准程序2编写的。
标准程序
/*
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int i,n,m,x,y,t,dfn[N],low[N];
vector <int> f[N];
void dfs(int fx){
int i,sx;dfn[fx]=low[fx]=++t;
for(i=0;i<f[fx].size();i++){
sx=f[fx][i];
if(dfn[sx]!=0) low[fx]=min(low[fx],low[sx]);
else dfs(sx),low[fx]=min(low[fx],low[sx]);
}
}
int main(){
cin>>n>>m;
for(i=1;i<=m;i++) cin>>x>>y,
f[x].push_back(y);
for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i);
for(i=1;i<=n;i++) cout<<dfn[i]<<" "<<low[i]<<"\n";
}
*/
//上面这段代码可能有错误，但是我认为是对的。
//下面这段代码是完全正确的
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int i,j,n,m,x,y,t,cnt,ans,fx,sx,fl,g[N],b[N],dfn[N],low[N],a[N],in[N];
vector <int> f[N];
stack <int> st;
void dfs(int fx){
int i,sx;dfn[fx]=low[fx]=++t;st.push(fx);in[fx]=1;
for(i=0;i<f[fx].size();i++){
sx=f[fx][i];
if(!dfn[sx]) dfs(sx),low[fx]=min(low[fx],low[sx]);
else if(in[sx]) low[fx]=min(low[fx],dfn[sx]);
}
if(dfn[fx]==low[fx]){
cnt++;
while(st.top()!=fx) a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop();
a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop();
}
}
int main(){
cin>>n>>m;
for(i=1;i<=m;i++) cin>>x>>y,
f[x].push_back(y);
for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i);
for(i=1;i<=n;i++) for(j=0;j<f[i].size();j++){
fx=i;sx=f[i][j];
if(a[fx]!=a[sx]) g[a[fx]]++;
}
for(i=1;i<=cnt;i++) if(g[i]==0) fl++,ans+=b[i];
for(i=1;i<=n;i++) cout<<dfn[i]<<" "<<low[i]<<"\n";
}P2：Tarjan缩点（"受欢迎的奶牛"的铺垫）
题目描述
问题描述：sd
给定一张n个点，m条边组成的有向图。对这张图锁点，输出每个点属于第几个强联通分量。N<=10000
加入in数组表示是否在栈内，同时考虑返祖边用dfn进行更新的情况。
输入：
第一行n和m。
接下来m行u和v，表示u到v的边。
输出：
1行n个整数。
样例输入：
3 3
1 2
2 1
2 3样例输出：
2 2 1题解报告
题目大意
给定一个有向图，要求使用Tarjan算法求出每个节点所属的强连通分量（SCC），并按节点顺序输出其所属SCC的编号。SCC的编号顺序根据发现的逆序排列，即最后一个发现的SCC编号最大。
算法思路
Tarjan缩点算法通过DFS遍历图，识别强连通分量并为其分配唯一编号：
DFS遍历：对每个未访问的节点启动DFS，维护dfn（访问时间戳）和low（当前节点能追溯的最早祖先的dfn）。
栈维护路径：用栈跟踪当前DFS路径上的节点，用in数组标记节点是否在栈中。
SCC识别：当回溯到某个节点且满足dfn[u] == low[u]时，该节点是当前SCC的根。将栈中节点弹出直到根节点，这些节点组成一个SCC，并分配唯一编号。
缩点记录：通过数组a记录每个节点所属的SCC编号。
标准程序
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int i,n,m,x,y,t,cnt,dfn[N],low[N],a[N],in[N];
vector <int> f[N];
stack <int> st;
void dfs(int fx){
int i,sx;dfn[fx]=low[fx]=++t;st.push(fx);in[fx]=1;
for(i=0;i<f[fx].size();i++){
sx=f[fx][i];
if(!dfn[sx]) dfs(sx),low[fx]=min(low[fx],low[sx]);
else if(in[sx]) low[fx]=min(low[fx],dfn[sx]);
}
if(dfn[fx]==low[fx]){
cnt++;
while(st.top()!=fx) a[st.top()]=cnt,in[st.top()]=0,st.pop();
a[st.top()]=cnt,in[st.top()]=0,st.pop();
}
}
int main(){
cin>>n>>m;
for(i=1;i<=m;i++) cin>>x>>y,
f[x].push_back(y);
for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i);
for(i=1;i<=n;i++) cout<<a[i]<<" ";
}P3：受欢迎的牛
题目描述
【题目描述】cow.cpp
每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
【输入】
第一行两个数 N,M；
接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。
【输出】
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
【输入样例】
3 3
1 2
2 1
2 3【输出样例】
1样例说明
只有第三头牛被除自己之外的所有牛认为是受欢迎的。
数据范围：
对于全部数据，1≤N≤10^4,1≤M≤5×10^4。
题解报告
题目大意
给定一个包含N头牛和M条单向认可关系的有向图。要求找出被除自己之外所有其他牛认可的牛的数量。认可具有传递性，即若A认可B，B认可C，则A也认可C。
算法思路
核心思路：将问题转化为图论中的强连通分量（SCC）问题：
缩点处理：使用Tarjan算法将图中的强连通分量缩为单个节点，形成有向无环图（DAG）。
出度统计：在缩点后的DAG中，统计每个缩点的出度。
结果判定：若存在且仅存在一个出度为0的缩点，则该缩点包含的牛的数量即为答案；否则无解。
关键性质：
在DAG中，出度为0的节点是唯一可能被所有其他节点到达的节点。
若存在多个出度为0的节点，则这些节点之间无法相互到达，无法满足题意。
标准程序
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int i,j,n,m,x,y,t,cnt,ans,fx,sx,fl,g[N],b[N],dfn[N],low[N],a[N],in[N];
vector <int> f[N];
stack <int> st;
void dfs(int fx){
int i,sx;dfn[fx]=low[fx]=++t;st.push(fx);in[fx]=1;
for(i=0;i<f[fx].size();i++){
sx=f[fx][i];
if(!dfn[sx]) dfs(sx),low[fx]=min(low[fx],low[sx]);
else if(in[sx]) low[fx]=min(low[fx],dfn[sx]);
}
if(dfn[fx]==low[fx]){
cnt++;
while(st.top()!=fx) a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop();
a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop();
}
}
int main(){
cin>>n>>m;
for(i=1;i<=m;i++) cin>>x>>y,
f[x].push_back(y);
for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i);
for(i=1;i<=n;i++) for(j=0;j<f[i].size();j++){
fx=i;sx=f[i][j];
if(a[fx]!=a[sx]) g[a[fx]]++;
}
for(i=1;i<=cnt;i++) if(g[i]==0) fl++,ans+=b[i];
if(fl==1) cout<<ans;
else cout<<0;
}
