【反图+拓扑排序】ABC245 F

港控/mmm° 2024-03-17 14:42 81阅读 0赞

[F - Endless Walk (atcoder.jp)][F - Endless Walk _atcoder.jp]

题意：

![d16bb1668bd54708a8ff49cdaf989c98.png][]

思路：

**首先，我们什么时候需要建反图：在一个有向图中，我们需要找出可以到达指定的结点的结点时，我们可以建立反图**

这道题中，我们需要找出所有能够到达环的结点，因此我们先建立反图，然后做一遍拓扑排序，剩下的点就是原来的图中所有能够到达环的结点（感性理解即可）

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    struct Graph{
    	int to,next;
    }edge[mxe<<2];
    
    queue<int> Q;
    
    int N,M,u,v,tot=0,ans;
    int head[mxn],in[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void topsort(){
    	for(int i=1;i<=N;i++){
    		if(!in[i]) Q.push(i);
    	}
    	while(!Q.empty()){
    		int u=Q.front();
    		Q.pop();
    		ans--;
    		for(int i=head[u];~i;i=edge[i].next){
    			in[edge[i].to]--;
    			if(!in[edge[i].to]) Q.push(edge[i].to);
    		}
    	}
    }
    void solve(){
    	cin>>N>>M;
    	ans=N;
    	G_init();
    	for(int i=1;i<=M;i++){
    		cin>>u>>v;
    		add(v,u);
    		in[u]++;
    	}
    	topsort();
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[F - Endless Walk _atcoder.jp]: https://atcoder.jp/contests/abc245/tasks/abc245_f
[d16bb1668bd54708a8ff49cdaf989c98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c5a52525889842f48f148cc695cb48e7.png