用 $tarjan$ 缩点（求强连通分量）写的 p2002消息扩散

本蒟蒻用的 $vector$ 来存边

也对照大佬们的题解检查了多次但不知道错在哪 :(

求大佬传授真理Orz

30分其他全 WA 记录详情

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;//最大城市数
const int M = 5e5 + 3;//最大边数（没用）
int n, m;
vector<int> vn[N];//向量记录边，vn[i]记录了城市i所有的出边
int cn, cg;//分别用于城市计数和强连通分量计数
int ng[N];//记录每个城市对应强连通分量的编号
stack<int> s;//tarjan用栈
int dfn[N], low[N];//tarjan
bool vis[N];//记录是否在栈内
int ans;//答案，计数有多少个入度为0的强连通分量
int in[N];//记录每个强连通分量入度

void tarjan(int x)//计算城市x
{//这算一个标准tarjan吧
	dfn[x] = low[x] = ++cn;//城市计数器++
	s.push(x);
	vis[x] = 1;//入栈标记
	
	for (int i=0; i<vn[x].size(); ++i)//遍历城市x每一条出边
	{
		int v = vn[x][i];//城市x的出边i所指向的城市v
		if (!dfn[v])//若v未被搜索过
		{
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if (vis[v])//若v在栈内
			low[x] = min(low[x], dfn[v]);
	}
	if (dfn[x] == low[x])
	{
		int t;
		cg++;//强连通分量个数++
		while (!s.empty())
		{
			t = s.top();
			s.pop();
			vis[t] = 0;//出栈标记

			ng[t] = cg;//记录城市t属于强连通分量cg
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i=1, u, v; i<=m; ++i) {
		scanf("%d%d", &u, &v);
		vn[u].push_back(v);//城市u有一条出边指向城市v
	}

	for (int i=1; i<=n; ++i)
		if (!dfn[i])
			tarjan(i);
	
	for (int i=1; i<=n; ++i)//遍历城市
	    for (int j=0; j<vn[i].size(); ++j)//枚举城市i出边
	        if (ng[i] != ng[vn[i][j]])//如果出边vn[i][j]两端城市不在同一个强连通分量
	            in[ng[vn[i][j]]]++;//对面城市所在强连通分量的入度++
	
	for (int i=1; i<=cg; ++i)//枚举每个强连通分量
	    if (!in[i])//若入度为0
	        ans++;
	cout << ans;
	return 0;
}