题目描述

难度分:$2700$

输入$T(\leq 10^6)$表示$T$组数据。所有数据的$n$之和$\leq 10^6$。

每组数据输入$n(1 \leq n \leq 10^6)$和长为$n$的数组$a(i-n \leq a[i] \leq i-1)$，下标从$1$开始。

求$a$的一个非空子集，满足子集元素和恰好等于$0$。

输出子集的大小，以及子集元素在$a$中的下标。多解输出任意解，下标的顺序不重要。允许子集有重复元素。

输入样例

2
5
0 1 2 3 4
4
-3 1 1 1

输出样例

1
1 
4
1 4 3 2 

算法

环图

思维难度很高的一个题，注意到$a[i]$的取值范围非常奇怪，移项后可以得到$i-a[i] \in [1,n]$，说明$i-a[i]$可以当做下标。然后构造一个图，从$i$向$i-a[i]$连一条有向边，图中任意一个环就是答案。

证明

对于一个环上的所有边$x[i] \rightarrow y[i]$，我们有$\Sigma x[i] =\Sigma y[i]$。

例如环$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$，我们有$1+2+3=2+3+1$。

对于本题建的图来说就是$\Sigma i = \Sigma(i-a[i])$

由于右边$= \Sigma i - \Sigma a[i]$，所以得到$\Sigma i = \Sigma i - \Sigma a[i]$

化简得$\Sigma a[i]=0$

复杂度分析

时间复杂度

建图只需要遍历$i \in [1,n]$，从$i$向$i-a[i]$连边，时间复杂度为$O(n)$。接下来遍历图找环，每个节点最多只会遍历一次，时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，还需要建立图的邻接表$g$，而每个节点只有一条出边，因此邻接表的空间复杂度为$O(n)$。在遍历图找环的时候需要一个布尔数组$st$来标记节点是否被访问过，每个节点都需要有一个标记位，因此空间复杂度也为$O(n)$。综上，算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1000010;
int T, n, a[N], g[N];
bool st[N];

void solve() {
    for(int x = 1; x <= n; x++) {
        if(!st[x]) {
            int start = x;
            st[x] = true;
            x = g[x];
            while(!st[x]) {
                st[x] = true;
                x = g[x];
            }
            if(st[x]) {
                vector<int> cycle;
                cycle.push_back(x);
                int start = x;
                x = g[x];
                while(x != start) {
                    cycle.push_back(x);
                    x = g[x];
                }
                printf("%d\n", cycle.size());
                for(int node: cycle) {
                    printf("%d ", node);
                }
                break;
            }
        }
    }
    puts("");
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            st[i] = false;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            g[i] = i - a[i];
        }
        solve();
    }
    return 0;
}