D14【模板】强连通分量 Tarjan 算法

20241219尝试教的新代码：

/*【参考程序】
强连通算法：最后得到cnt（图有多少个连通分量）和scc数组（scc[x]表示点x所属的连通分量的编号）
概念：
（1）、环：每个点都在若干个环中，单独一个点也是一个环。
（2）、环的发起点：某个环中遍历序号最小的那个点。
（3）、连通分量由若干个有共同点的环构成（共同点可能不只一个），这点等算法学完再理解不迟。
数据结构：
int tsp,low[N],dfn[N];
tsp为时间戳，即遍历的顺序值。每个点有两个属性low和dfn，
dfn[i]记录dfs过程中点i的遍历序号（不再变），
low[i]记录点i所在的环（之一）的发起点的时间戳 
stack<int> s;bool v[N];// s为栈，v[i]表示点i是否在栈里。
int cnt,scc[N];
算法过程：
1、在主函数中，所有点逐个问一遍，遇到没有遍历过的点就tarjan（即dfs） 
2、tarjan(x)过程：
（1）、x是新点（还没遍历过），先赋值x的dfn和low值且x进栈。
（2）、然后访问所有和x直接相连的点y。
    如果y还没有遍历过：则tarjan(y),回来后问y有没有遇到已经遍历过且没有出栈的点？如果有则可以更新low[x];
    如果y已经遍历过：如果y还在栈里面（否则y属于另外一个连通分量），则x和y在同一个环（重点），且y是环的发起点（重点）（注：x以后有可能遇到编号值更小（更早）环发起点）。
（3）、完成（2）后，检查x的两个属性是否依旧相同。如果是，则x为新连通分量的发起点。且在栈中x之上的所有点都是和x在同一个连通分量。
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
vector<pair<int,int>>G[N];
int tsp,cnt,low[N],dfn[N],scc[N];;
stack<int>stk;bool instk[N];

void tarjan(int x,int in_id) // 当前访问x（x之前没有被访问过）
{
	dfn[x]=low[x]=++tsp; //新点x一开始dfn和low都等于tsp
	stk.push(x);instk[x]=1; //新点进栈 
    for(auto i:G[x])if(i.second!=in_id)
    {
        int y=i.first,id=i.second;
        if(dfn[y]==0) //如果点y还没访问过，
        {
            tarjan(y,id);//递归y
            low[x]=min(low[x], low[y]);//然后再问y是否遇到了还没出栈的环发起点
        }
        else if(instk[y]==1) //如果点y已经被访问过，并且还没有出栈
		{//在这之前有y->x的路径，现在x到y有边，所以y和x在同一个环中，且y是环的发起点
			low[x]=min(low[x], dfn[y]);
		}
    }
    if(low[x]==dfn[x]) //此时说明x可作为新连通分量的发起点，样例2说明
    {
        cnt++;//cnt++，表示又多了一个新的连通分量
        for(int z=-1;z!=x;)
		{
			z=stk.top();stk.pop();instk[z]=0;//出栈标记z已经出栈
            scc[z]=cnt;//标记z所属连通分量的标号
        }
    }
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back({y,i});
	
	tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	memset(instk,0,sizeof(instk));memset(scc,0,sizeof(scc));
	for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,0);
	printf("%d\n",cnt);
	return 0;
}