P2002 消息扩散

题意:简单缩点,显然答案是执行完Tarjan算法后,新图中入度为0的点的数目
显然,缩点完成后出现的重边不会影响入度为0的点的计算,因为重边只会让$deg[v]$重复地增加,并不会使得$deg[v]==0$的数目增加,所以就这样写就可以了

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
int dfn[maxn],low[maxn],dfs_clock=0;int scc[maxn],scc_cnt;
stack<int> S;
void dfs(int u){
	low[u] = dfn[u] = ++dfs_clock;
	S.push(u);
	for(auto v : G[u]){
		if(!dfn[v]){
			dfs(v);
			low[u] = min(low[u],low[v]);
		}
		else if(!scc[v]) low[u] = min(low[u],dfn[v]);//不是cross_edge而是back_edge的情况更新
	}
	if(low[u]==dfn[u]){
		scc_cnt++;
		while(true){
			int x=S.top();S.pop();
			scc[x]=scc_cnt;
			if(x==u) break;
		}
	}
}
//int to[maxn],head[maxn*2],nxt[maxn*2],tot=1;
//void add(int u,int v){
//	to[++tot] = v,nxt[tot] = head[u],head[u] = tot;
//}
int deg[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	vector<pii> edge;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		G[u].pb(v);
		edge.push_back({u,v});
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) dfs(i);
 	}
 	for(auto [u,v]:edge){
 		if(scc[u]!=scc[v]) deg[scc[v]]++;
	}
	int cnt = 0;
	for(int i=1;i<=scc_cnt;i++) cnt+=(!deg[i]);
	cout<<cnt<<"\n"; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65