乌龟与洞穴（并查集）

题目：

辽阔的太平洋上有一个十分美丽的岛。

岛的海岸上有 n 个洞穴呈环形分布（从逆时针编号0到n-1），有一只乌龟生活在岛上，它早上都会外出觅食，晚上都会回到岛上，然后寻找洞穴睡觉。但是，这只乌龟不会去寻找之前睡过的洞穴入睡，因此每天都需要消耗大量的时间去寻找洞穴。

现在给你 n 天晚上乌龟回来的洞穴位置，你能帮助它寻找每天入睡的洞穴吗？

注意：乌龟只会沿逆时针寻找洞穴。

第一行包含一个整数 (1 < T < 1000) 代表测试组数，对于每一组测试：

第一行一个整数 n (1 < n < 10^5) 表示洞穴的个数以及总共的天数。

第二行 n 个整数 a_i (0 < a_i < n-1) 表示第 i 天回来的洞穴位置。

数据保证所有测试中 n 的和不超过 10^6。

对于每组测试，输出一行，包含 n 个整数，第 i 个整数表示第 i 天乌龟入睡的洞穴的编号。

Sample Input

Sample Output

解题思路

首先说明一下，我这之前对于并查集几乎是一无所知，或者只是知道一个名字而已。

看到这道题，第一反应是，这道题不算难吧，是不是暴力可做……然后我就暴力做了，当然了，暴力肯定要超时。

然后说一说不暴力要怎么做吧。

在不知道并查集的情况下，我能想到的是根据java中的引用传递的思想：

在java中，new出来的对象一般情况下都是保存在heap（堆）中的，而java程序中对变量的使用一般叫“引用”。如果这样写obj1=obj2;，其实就是将obj1的引用指向了obj2的引用，之后如果对obj1或obj2其中一个进行改变的话，另外一个也会改变。比如：
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
StringBuffer str1=new StringBuffer("1");
StringBuffer str2=new StringBuffer("2");
/*
 *此时，
 *str1->1
 *str2->2
 */
str1=str2;//改变str1的引用地址
/*
 *str1->2
 *str2->2
 */
str2.append("s");//改变str2所引用的值
/*
 *str1->2s
 *str2->2s
 */
以上代码就表明了刚刚说的引用传递的具体实现，如果有兴趣可以copy下来试试。

知道这个思想了，然后呢？在这里，大家不难发现，例如上例中，我改变了str2的值，str1的值也随之改变，且改变以后的值仍旧与str2相同，如果把每次乌龟住过的洞穴都改变它的引用，使其指向下一个没有住过的洞穴，然后如果有重复询问相同洞穴的话，我们还可以看做是访问相同的洞穴（其实只是名字相同，引用已经改变了），这样其实每次寻路肯定要比暴力的寻路要短得多，具体短多少或者说最坏的情况我还没有计算过，但是只要是有优化就比暴力好。

可能我上面说的思路你还是没有懂，我们来看样例输入中的第一个例子吧，直接用它来展现这个的思想：

洞穴编号->实际访问

洞穴编号 0 1 2 3 4 5

实际访问 0 1 2 3 4 5

第一次访问 4

洞穴编号 0 1 2 3 4 5

实际访问 0 1 2 3 5 5

编号为4的洞穴引用指向了编号为5的洞穴

第二次访问 5

洞穴编号 0 1 2 3 4 5

实际访问 0 1 2 3 0 0

编号为5的洞穴引用指向了编号为0的洞穴，又因为编号为4的洞穴指向了编号为5的洞穴，所以编号为4的洞穴也同时指向了编号为0的洞穴（当然，这里并没有真正的实现，目前只能从访问的那位开始往下递归）

第三次访问 5

洞穴编号 0 1 2 3 4 5

实际访问 1 1 2 3 1 1

因为编号为5的洞穴引用指向了编号为0的洞穴，所以乌龟实际是住在了编号为0的洞穴，然后所有指向编号为0的洞穴都指向了编号为1的洞穴

第四次访问 0

洞穴编号 0 1 2 3 4 5

实际访问 2 2 2 3 2 3

同上

第五次访问 4

洞穴编号 0 1 2 3 4 5

实际访问 3 3 3 3 3 3

倒数第二次访问，实际上仅有最后一个洞穴未住，因此所有的洞穴都统一指向了编号为3的洞穴

第五次访问 3

程序结束

洞穴编号	0	1	2	3	4	5
实际访问	0	1	2	3	4	5

洞穴编号	0	1	2	3	4	5
实际访问	0	1	2	3	5	5

洞穴编号	0	1	2	3	4	5
实际访问	0	1	2	3	0	0

洞穴编号	0	1	2	3	4	5
实际访问	1	1	2	3	1	1

洞穴编号	0	1	2	3	4	5
实际访问	2	2	2	3	2	3

洞穴编号	0	1	2	3	4	5
实际访问	3	3	3	3	3	3

上面这个图就大概画出了我期望的效果，当然，期望的效果还是没有达到，最后我还是只能使用递归来改变所有的引用指向。其实在第二次访问5的时候，编号为4的洞穴就那里就开始是期望状态了，而实际上，即使第二次访问了5，因为4在5之前，所以4的引用指向并不会改变，但是在下一次访问到4的时候，程序可以递归查找到5号洞穴，然后实际访问的就是和访问5号洞穴是一样的效果。

解题代码

我分别用java和C语言实现了这个程序的代码，但是java的总是要报RE，我也不知道那里错了，可以参考一下。

cpp

#include 
#include
 
struct Tong
{
    int id;
};
 
struct Tong tongs[100005];
int n;
struct Tong saveTong(int x);
int flag;
int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        memset(tongs,0,sizeof(tongs));
        flag=1;
        scanf("%d",&n);
 
        for(i=0;i
            tongs[i].id=i;
        }
 
        for(i=0;i
            int x;
            scanf("%d",&x);
            if(n==1){
                printf("0");
                continue;
            }
            saveTong(x);
        }
        printf("\n");
    }
    return 0;
}
 
struct Tong saveTong(int x){
    if(tongs[x].id==x){
        if(flag!=1){
            printf(" %d",x);
        }
        else
        {
            printf("%d",x);
            flag=0;
        }
         
        int y=x+1;
        if(y>=n){
            y=0;
        }
        tongs[x]=tongs[y];
    }else{
        tongs[x]=saveTong(tongs[x].id);
    }
    return tongs[x];
}

java

import java.util.Scanner;
 
public class Main {
    static class Tong{
        int id;
        boolean isSave=true;
        public Tong(int id) {
            this.id = id;
        }
    }
    static int n;
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args) {
        int t = sc.nextInt();
        while(t-->0){
            n=sc.nextInt();
            Tong[] tong=new Tong[n+5];
            for (int i=0;i
                tong[i]=new Tong(i);
            }
            for (int i=0;i
                int x=sc.nextInt();
                if (n==1){
                    System.out.print('0'+" ");
                    continue;
                }
                saveTong(tong,x);
//                System.out.println(tong[x].id);
            }
            System.out.println();
        }
    }
    /***
     * 功能描述 递归的开始
     * @author pang
     * @date 19-4-18 下午2:08
     * @parm [tongs, x]
     * @return Main.Tong
    */
    static Tong saveTong(Tong[] tongs,int x){
        if (tongs[x].isSave&&tongs[x].id==x){
            System.out.print(x+" ");
            tongs[x].isSave=false;
            int y=x+1;
            if (y>=n){
                y=0;
            }
            tongs[x]=tongs[y];
        }else {
            tongs[x]=saveTong(tongs,tongs[x].id);
        }
        return tongs[x];
    }
}

题目：

Description

Input

Output

解题思路

解题代码