题解 P2002 【消息扩散】

刚学tarjan，写篇题解加深下印象。

tarjan算法详解

给定一张有向图，求它的所有强连通分量。

每次选择一个未遍历的点开始dfs。

定义dfn[i]表示i被遍历到的时间，low[i]表示从i出发，只经过至多一条dfn变小的边，能走到的dfn最小的点的dfn的值。（可能有些绕，看不懂建议多看几遍）

维护一个栈，dfs到一个点时将它加入栈内。

如果一个点的dfn=low，那么不停弹出栈顶元素直到这个点被弹出，被弹出的所有点就构成了一个强连通分量。

时间复杂度O(m),m是边数

---

思路：先用tarjan缩点，然后统计入度为0的点的个数（缩点指将每一个强连通分量缩成一个点）

这里有一个小技巧，可以不用在缩点后重新建图，直接统计入度即可

code:

#include<iostream>
#include<vector>
using namespace std;
#define N 100005
int dfn[N],low[N],tim=1,stack[N],top=0,belong[N],pn=0,du[N];
bool in[N];
vector<int> a[N];
void tarjan(int u){
	low[u]=tim;
	dfn[u]=tim++;
	stack[top++]=u;
	in[u]=true;//先初始化dfn值和low值，并压入栈
	int siz=a[u].size(),v;
	for(int i=0;i<siz;i++){
		v=a[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in[v]) 
			low[u]=min(low[u],low[v]);//递归并更新low值
	}
	if(dfn[u]==low[u]){
		pn++;
		while(stack[top]!=u){
			top--;
			belong[stack[top]]=pn;
			in[stack[top]]=false;
		}
	}//将强连通分量中的点打上标记
}
int main()
{
	int n,m,x,y,ans=0;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		if(x!=y)
			a[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);//如果没有遍历过，那就遍历它
	for(int i=1;i<=n;i++)
		for(int j=0;j<a[i].size();j++)
			if(belong[i]!=belong[a[i][j]])
				du[belong[a[i][j]]]++;//统计入度
	for(int i=1;i<=pn;i++)
		ans+=(du[i]==0);//统计答案
	cout<<ans;
	return 0;
}