题目链接：https://codeforces.com/contest/1368/problem/E
给出一个 $n$ 点 $m$ 边的有向图，每条边由编号较小的点通向编号较大的点，每个点的出度不大于 $2$，删掉一些点，使得图中不存在长度大于等于 $2$ 的路径。（最多删掉 $\frac{4}{7}n$ 个点）
删除所有长度为 $2$ 的路径的末端点。
删除点占比最大的情况是该有向图为满二叉树且深度为 $3$ 的倍数，要删除的点即深度为 $3$ 的倍数每层结点，恰好为 $\frac{4}{7}n$ 。
#include <bits/stdc++.h> using namespace std; void solve() { int n, m; cin >> n >> m; vector<int> G[n + 1]; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; if (u == v) continue; G[u].push_back(v); } vector<int> ans; int dis[n + 1] = {}; for (int u = 1; u <= n; u++) { if (dis[u] == 2) ans.push_back(u); else for (auto v : G[u]) dis[v] = max(dis[v], dis[u] + 1); } cout << ans.size() << "\n"; for (auto i : ans) cout << i << " \n"[i == ans.back()]; } int main() { int t; cin >> t; while (t--) solve(); }
Codeforces Global Round 8 E. Ski Accidents
原文：https://www.cnblogs.com/Kanoon/p/13168766.html