题解 CF1270G 【Subset with Zero Sum】

xht

2019-12-31 17:03:06

Solution

由于 $i - n \le a_i \le i - 1$,所以 $1 \le i - a_i \le n$。 建立一张 $n$ 个点的有向图,对于每个点 $i$,连边 $i \to i - a_i$。 这张图中每个点的出度都为 $1$,因此这张图是一个基环内向森林。 可以发现对于任意一个环,环上的点对应的下标就是我们要找的答案。 ```cpp const int N = 1e6 + 7; int n, x, t[N], v[N]; inline void solve() { rd(n); for (int i = 1; i <= n; i++) rd(x), t[i] = i - x, v[i] = 0; x = 1; while (!v[x]) v[x] = 1, x = t[x]; vi ans; ans.pb(x), x = t[x]; while (x != ans[0]) ans.pb(x), x = t[x]; print(ans.size()); while (ans.size()) print(ans.back(), " \n"[ans.back()==ans[0]]), ans.pop_back(); } int main() { int T; rd(T); while (T--) solve(); return 0; } ```