【題解】Codeforces 1270G. Subset with Zero Sum

【範例】水母圖找環
【題目敘述】http://codeforces.com/contest/1270/problem/G

#include <iostream>
#include <vector>
using namespace std;
 
const int maxn = 1000005;
int t, n, a[maxn], vis[maxn];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            a[i] = i-a[i];
            vis[i] = 0;
        }
        int cur = 1;
        while (!vis[cur]){
            vis[cur] = 1;
            cur = a[cur];
        }
        vector <int> ans;
        while (vis[cur]){
            ans.push_back(cur);
            vis[cur] = 0;
            cur = a[cur];
        }
        cout << ans.size() << "\n";
        for (int i:ans){
            cout << i <<  " ";
        }
        cout << "\n";
    }
}
分享本文 Share with friends