本文主要是介绍AtcoderBeginerContest245.F EndlessWalk 反图+拓扑排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
|–>传送门<–|
题目大意
给定一个 n n n个节点, m m m条边的简单有向图,问有多少个节点满足作为起点出发时能够到达一个环中。
数据范围 ( n , m ≤ 2 × 1 0 5 ) (n, m \leq 2 \times 10^5) (n,m≤2×105)。
题解
首先容易发现,对于一个图,如果没有向外的一条出边,那么该图上所有的点一定可以进环(感性理解)。
例如上图,橙色点就是一个被唯一出边指向的点。
那么我们记录所有点的出度,然后根据出度直接跑拓扑排序即可。但注意要建反图,否则从连通块能跑出去,但找不到进来的路,相当于把题目给做反了。
#include <bits/stdc++.h>
#define int long longconst int N = 2e5 + 10;
std::vector<int> g[N];
int out[N];inline void solve(){int n = 0, m = 0, cnt = 0; std::cin >> n >> m;for(int i = 1, u, v; i <= m; i++){std::cin >> u >> v;g[v].emplace_back(u);out[u]++;}std::queue<int> q;for(int i = 1; i <= n; i++) if(!out[i]) q.emplace(i);while(q.size()){int now = q.front(); q.pop();for(int nxt : g[now]){out[nxt]--;if(!out[nxt]) q.emplace(nxt);}cnt++;}std::cout << (n - cnt) << '\n';
}signed main(){solve();return 0;
}
这篇关于AtcoderBeginerContest245.F EndlessWalk 反图+拓扑排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!