算法
(构造) $O(N(N + M))$
若图中无环,则显然无解
若图中有环,则只需找出其中的最小环即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
using P = std::pair<int, int>;
template<typename T1, typename T2>
inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
}
const int INF = 1001001001;
auto bfs = [&](auto& f, int sv) -> vector<int> {
vector<int> dist(n, INF), pre(n, -1);
queue<int> q;
dist[sv] = 0;
q.push(sv);
while (q.size()) {
int v = q.front(); q.pop();
for (int u : to[v]) {
if (dist[u] != INF) continue;
pre[u] = v;
dist[u] = dist[v] + 1;
q.push(u);
}
}
P best(INF, -1);
rep(v, n) {
if (v == sv) continue;
for (int u : to[v]) {
if (u == sv) {
chmin(best, P(dist[v], v));
}
}
}
if (best.first == INF) return vector<int>(n+1);
int v = best.second;
vector<int> res;
while (v != -1) {
res.push_back(v+1);
v = pre[v];
}
return res;
};
vector<int> ans(n+1);
rep(s, n) {
auto now = bfs(bfs, s);
if (now.size() < ans.size()) ans = now;
}
if (ans.size() == n + 1) {
puts("-1");
return 0;
}
cout << ans.size() << '\n';
for (int v : ans) {
cout << v << '\n';
}
return 0;
}
// O(N) 解法
// 1. 找到 dfs 中的任何一个环
// 2. 按照这个顺序遍历环中的每一个顶点 v,对于从 v 指向的下一个点 w,如果 w 是环中的一个顶点,
// 将 v 和 w 之间的顶点从环中移除,并将 v 之后的下一个顶点改为 w。
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using vi = vector<int>;
int main() {
int n, m;
cin >> n >> m;
vector<vi> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
}
vi vs;
vi state(n);
auto dfs = [&](auto& f, int v) -> bool {
if (state[v]) {
if (state[v] == 1) {
vs.erase(vs.begin(), find(vs.begin(), vs.end(), v));
return true;
}
return false;
}
vs.push_back(v);
state[v] = 1;
for (int u : to[v]) {
if (f(f, u)) return true;
}
state[v] = -1;
vs.pop_back();
return false;
};
auto solve = [&] {
vector<int> nxt(n), visited(n), erased(n, 1);
rep(i, vs.size()) {
int v = vs[i];
int u = vs[(i+1)%vs.size()];
nxt[v] = u;
erased[v] = 0;
}
int v = vs[0];
while (!visited[v]) {
for (int u : to[v]) {
if (erased[u]) continue;
int nv = v;
while (nxt[nv] != u) {
nv = nxt[nv];
erased[nv] = 1;
}
nxt[v] = u;
}
visited[v] = 1;
v = nxt[v];
}
vi ans;
int sv = v;
while (1) {
ans.push_back(v);
v = nxt[v];
if (v == sv) break;
}
cout << ans.size() << '\n';
for (int v : ans) cout << v+1 << '\n';
};
rep(i, n) if (!state[i]) {
if (dfs(dfs, i)) {
solve();
return 0;
}
}
puts("-1");
return 0;
}