Subset with Zero Sum (Codeforces 1270G)
Tags: Math, dfs and similar

You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, such that for each $$$1\le i \le n$$$ holds $$$i-n\le a_i\le i-1$$$.Find some nonempty subset of these integers, whose sum is equal to $$$0$$$. It can be shown that such a subset exists under given constraints. If there are several possible subsets with zero-sum, you can find any of them.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^6$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n \le 10^6$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$i-n \le a_i \le i-1$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output two lines.In the first line, output $$$s$$$ ($$$1\le s \le n$$$) — the number of elements in your subset.In the second line, output $$$s$$$ integers $$$i_1, i_2, \dots, i_s$$$ ($$$1\le i_k \le n$$$). All integers have to be pairwise different, and $$$a_{i_1} + a_{i_2} + \dots + a_{i_s}$$$ has to be equal to $$$0$$$. If there are several possible subsets with zero-sum, you can find any of them.

Note: In the first example, we get sum is $$$a_1 = 0$$$.In the second example, we get sum is $$$a_1 + a_4 + a_3 + a_2 = 0$$$.

Sample Inputs:
2
5
0 1 2 3 4
4
-3 1 1 1

Sample Outputs:
1
1 
4
1 4 3 2

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for test in range(t):
    n = int(input())
    A = list(map(int, input().split()))
    res = []
    s = set()
    cur = 1
    while not cur in s:
        res.append(cur)
        s.add(cur)
        cur = cur - A[cur - 1]
    x = res.index(cur)
    print(len(res[x:]))
    print(*res[x:])

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for test in range(t):
    n = int(input())
    A = list(map(int, input().split()))
    ANS = []
    SET = set()
    NOW = 1
    while not NOW in SET:
        ANS.append(NOW)
        SET.add(NOW)
        NOW = NOW - A[NOW - 1]
    x = ANS.index(NOW)
    print(len(ANS[x:]))
    print(*ANS[x:])

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count, product
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 5096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
t = II()
for _ in range(t):
    n = II()
    next_pos = [i - v for (i, v) in enumerate(MII())]
    vis = [0] * n
    pt = 0
    while not vis[pt]:
        vis[pt] = 1
        pt = next_pos[pt]
    ans = [pt]
    while next_pos[ans[-1]] != pt:
        ans.append(next_pos[ans[-1]])
    print(len(ans))
    print(*(x + 1 for x in ans))