拓扑排序的妙用
F - Endless Walk
题意：给定一个有向图，和一个条件：从某个点出发，能无限前进。问满足条件的点的个数。
分析：环上的点和能进入环的道路上的点符合无限前进的条件，其他的点均不符合。
题解：在拓扑排序中，queue中没法加入的点是环上的点和从环指向外面的点（没有切入点，in[i]无法减为0）。我们可以反向建图，这样满足条件的点就无法进入queue了，统计queue中出现过的点的个数cnt，输出 n - cnt 即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
#define TLE std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define int long long
#define endl "\n"
#define P pair<int, int>
int n, m;
void solve() {
cin >> n >> m;
vector<P> v(n);
vector<P> s(m);
for (int i = 0; i < n; i ++) cin >> v[i].first;
for (int i = 0; i < n; i ++) cin >> v[i].second;
for (int i = 0; i < m; i ++) cin >> s[i].first;
for (int i = 0; i < m; i ++) cin >> s[i].second;
sort(v.begin(), v.end(), greater());//从大到小
sort(s.begin(), s.end(), greater());
multiset<int> st;
for (int i = 0, j = 0; i < n; i ++) {
while (s[j].first >= v[i].first && j < m) st.insert(s[j].second), j ++;
auto it = st.lower_bound(v[i].second);
if (it == st.end()) {
cout << "No\n";
return ;
}
st.erase(it);
}
cout << "Yes\n";
}
signed main() {
TLE;
solve();
return 0;
}
View Code
E - Find PermutationA
题意：给出$m$对$x, y$，问能否确定$n$的唯一排序$A$，使得每对$x_i, y_i$满足 $A_{x_i} < A_{y_i}$.
$2 <= N <= 2*10^5, 1 <= M <= 2 * 10 ^5$
思考角度：建图。如果有环，那么就会有矛盾；如果图被分成了多个部分，那么每个部分之间没法判断大小关系，因此只能由一个连通部分。这个部分能否包含多条链，显然不行，多条连的部分之间无法判断大小关系。所以最终只能是一条直链，中间的每个元素都有一个前驱和后继，代表第i个数出现的位置。用拓扑排序去排除这些情况即可。
题解：每对$x, y$之间都建立一条$x$ -> $y$的边，代表 $x$位置的数要小于$y$位置的数。
如果给出的条件能够确定唯一排序，那么对于每一个数$i (1 <= i < n)$，其出现位置$pos$指向$i + 1$出现位置的边一定会给出，这样菜能构成了一条代表$1$~$n$出现位置的链。
构造出来的图，不能有如下情况：
-
存在环 （1）
-
存在多条链
-
多条边汇入一个点的情况 （2）
-
一个点流出多条分支的情况 （3）
-
以上这些在拓扑排序过程中需要排除掉。
第（1）条根据最后每个点的$in[i]$是否为0判断得到；
第（2）条根据最初是否有多个入度为0的点判断得出；
第（3）条根据拓展一个节点时，是否有多个子节点$--in[i]$得到0，得出；
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
#define TLE std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define endl "\n"
#define P pair<int, int>
#define int long long
#define inf 1e18
int n, m;
int in[maxn];
vector<int> G[maxn];
int ans[maxn];
int vis[maxn];
//拓扑排序有向图判环
void topsort() {
queue<int> q;
int cnt = 0;
for (int i = 1; i <= n; i ++) {
if (!in[i]) {
q.push(i);
cnt ++;
}
}
if (cnt > 1) {cout << "No\n";return ;}
int tot = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
ans[x] = ++ tot;
int t = 0;
for (auto i : G[x]) {
in[i] --;
if (!in[i]) {q.push(i); t ++;}
}
if (t > 1) {cout << "No\n"; return ;}
}
if (tot != n) {cout << "No\n"; return ;}
cout << "Yes\n";
for (int i = 1; i <= n; i ++) cout << ans[i] << " \n"[i == n];
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
int x, y;
cin >> x >> y;
in[y] ++;
G[x].push_back(y);
}
topsort();
}
signed main() {
TLE;
int T = 1;
// cin >> T;
while (T --) {
solve();
}
return 0;
}
View Code
标签：std,妙用,int,拓扑,cin,++,排序,define From： https://www.cnblogs.com/coding-inspirations/p/17185403.html