学习了一下强连通分量，整理一下：
强连通分量的概念：任意两点之间能相互到达。
缩点简单来讲就是缩环成点，把强连通分量用一个点来维护，形成有向无环图。
缩点方式有三种这里只说一下。
求缩点：时间复杂度
单纯判断是否有环一般可以用，那么在搜索过程中我们对点只有三种情况：
1.该点没有搜索过。
2.该点有搜索过，但是不是我们上一个遍历的点的祖宗节点。
3.该点有搜索过，是我们上一个遍历节点的祖宗节点。
下图描述了三种情况：黑色边为，绿色边为，蓝色边为。
显然，只有第三种边能成环，成环的这些为强连通分量，其他的单独一个点作为强连通分量（自己本身就能到达自己），所以上图的强连通分量为（{1}，{2，3}，{4}，{5}）四个。
但是实际情况可能有很多个环嵌套，所以我们不能判断当前为环后，直接进行缩点，应该所有该子节点环判断完后，一块缩点。
为了解决这种问题，我们引入一个 （时间戳）来记录我们第一次到达每个节点的顺序，一个 （当前节点所接触到的最早的时间戳节点，初始为当前节点的 值），在回溯的过程中对当前节点与其子节点取值来实现维护最大强连通分量集合，一个栈存我们 过程的节点。
因为 的时候说明此节点为一个强连通分量的最早结点，那么我们可以开始从栈头开始 ，直到栈头等于当前节点，那么取出的节点即为我们所维护的一个强连通分量集合。
具体细节可以看代码：
int dfn[N],low[N],cnt,sz[N],scc[N],sc;
stack<int>st;
vector<int>e[N];
bool vis[N];
void tarjan(int u){
dfn[u]=low[u]=++cnt;
st.push(u),vis[u]=true;
for(auto &to:e[u]){
if(!dfn[to]){
tarjan(to);
low[u]=min(low[u],low[to]);
}
else if(vis[to]){
low[u]=min(low[u],dfn[to]);
}
}
if(dfn[u]==low[u]){
sc++;
while(st.top()!=u){
sz[sc]+=w[st.top()];
scc[st.top()]=sc;
vis[st.top()]=0;
st.pop();
}
sz[sc]+=w[st.top()];
scc[st.top()]=sc;
vis[st.top()]=0;
st.pop();
}
}
例题：P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
给定一个 个点 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入格式
第一行两个正整数
第二行 个整数，其中第 个数 表示点 的点权。
第三至 行，每行两个整数 ，表示一条 的有向边。
输出格式
共一行，最大的点权之和。
样例 #1
样例输入 #1
2 2
1 1
1 2
2 1
样例输出 #1
2
提示
对于 的数据，，，。
思路：
因为是有向图，所以可能存在有环的情况，因为每个点可以走多次，所以只要是路径上有环，我们全部取掉为最优。所以直接用缩点，重新建图，把图变为有向无环图，新缩成的点的权值为全部点的点权和。那么该题就变成了，给你一个，和每个点的点权，求点权最长路径。直接在新图的拓扑序中dp维护权值即可。
int dfn[N],low[N],cnt,sz[N],scc[N],sc,d[N],dp[N],ans,w[N];
stack<int>st;
vector<int>e[N],ex[N];
bool vis[N];
queue<int>q;
void tarjan(int u){
dfn[u]=low[u]=++cnt;
st.push(u),vis[u]=true;
for(auto &to:e[u]){
if(!dfn[to]){
tarjan(to);
low[u]=min(low[u],low[to]);
}
else if(vis[to]){
low[u]=min(low[u],dfn[to]);
}
}
if(dfn[u]==low[u]){
sc++;
while(st.top()!=u){
sz[sc]+=w[st.top()];
scc[st.top()]=sc;
vis[st.top()]=0;
st.pop();
}
sz[sc]+=w[st.top()];
scc[st.top()]=sc;
vis[st.top()]=0;
st.pop();
}
}
void topu(){
for(int i=1;i<=sc;i++)if(!d[i])q.push(i),ans=max(ans,(dp[i]=sz[i]));
while(q.size()){
int ver=q.front();
q.pop();
for(auto &to:ex[ver]){
d[to]--;
dp[to]=max(dp[to],dp[ver]+sz[to]);
ans=max(ans,dp[to]);
if(!d[to])q.push(to);
}
}
}
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
e[u].pb(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;i++){
int u=scc[i];
for(auto &to:e[i]){
int v=scc[to];
if(u==v)continue;
ex[u].pb(v);
d[v]++;
}
}
topu();
cout<<ans<<"\n";
}
[P2812 校园网络【USACO]Network of Schools加强版】 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目背景
浙江省的几所 OI 强校的神犇发明了一种人工智能，可以 AC 任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。
题目描述
共有 所学校 已知他们实现设计好的网络共 条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。
输入格式
第一行一个正整数 。
接下来 行每行有若干个整数，用空格隔开。
第 行，每行输入若干个非零整数 ，表示从 到 有一条线路。以 作为结束标志。
输出格式
第一行一个整数，表示至少选几所学校作为共享软件的母机，能使每所学校都可以用上。
第二行一个整数，表示至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。
样例 #1
样例输入 #1
5
2 0
4 0
5 0
1 0
0
样例输出 #1
2
2
提示
实际上，，$1\le $ 边数 。
思路：
依旧是缩点形成，对于第一个问题：入度为零的点个数即为最少学校，因为入度为零的点为每一个联通图的初始节点。对于第二个问题：(入度为零的点,出度为零的点）即为答案，因为要整体成强连通分量只能把所有把现有的边入度和出度都为零，因为连接一条边是入度出度都++，所以输出入度或者出度即可。
代码：
int dfn[N],low[N],cnt,sz[N],scc[N],sc,d[N],ud[N];
stack<int>st;
vector<int>e[N],ex[N];
bool vis[N];
queue<int>q;
void tarjan(int u){
dfn[u]=low[u]=++cnt;
st.push(u),vis[u]=true;
for(auto &to:e[u]){
if(!dfn[to]){
tarjan(to);
low[u]=min(low[u],low[to]);
}
else if(vis[to]){
low[u]=min(low[u],dfn[to]);
}
}
if(dfn[u]==low[u]){
sc++;
while(st.top()!=u){
scc[st.top()]=sc;
vis[st.top()]=0;
st.pop();
}
scc[st.top()]=sc;
vis[st.top()]=0;
st.pop();
}
}
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++){
int x;
while(cin>>x,x){
e[i].pb(x);
}
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
int ans1=0,ans2=0;
for(int i=1;i<=n;i++){
int u=scc[i];
for(auto &to:e[i]){
int v=scc[to];
if(u==v)continue;
d[v]++,ud[u]++;
}
}
for(int i=1;i<=sc;i++)
{
if(!d[i])ans1++;
if(!ud[i])ans2++;
}
cout<<ans1<<"\n";
if(sc==1)
cout<<0<<"\n";
else cout<<max(ans1,ans2)<<"\n";
}