一、题目

小军的军训进行到了一半了，今天军训教官搞了一波突然袭击，进行了一个寝的查。

提前了解到查寝消息的小军准备进行一波整理归纳，来使自己的寝室变得更加整洁。具体来说，小军有n件物品，放在n个盒子里，第i个盒子有物品i，小军会进行m次整理，第i次整理，小军会依次在第x个盒子顶拿走物品放入第y个盒子内，直至第x个盒子完全搬空。比如第1个盒子自顶向下有物品1、2，第2个盒子有物品3，将盒子1内的物品搬入盒子2内后结果是： 第1个盒子没有物品，第2个盒子自顶向下是2、1、3

现在，小军告诉你n还有m次操作具体是什么，你能告诉他最后每个盒子内有几个物品，他们具体是什么么？

输入：

一个正整数n代表盒子和物品数，一个正整数m代表整理归纳的次数

接下来m行输入，一行两个正整数x y，代表用上述的方法将盒子x的物品搬到盒子y里

1≤n≤10^5, 1≤m≤10^6, 1≤x,y≤n

题目保证x != y

输出；

有n行输出

第i行，先输出一个正整数k，表示第i个盒子内的物品数，接下来输出n个数，表示第i个盒子自顶向下的物品标号

注意：

行末无空格，文末有回车。

---

二、AC代码及注释

因为考虑顺序的话会用到链表，非常麻烦，所以我们不记盒内物体顺序，直接边输入、边操作、边存储每个盒子内最头和最尾两个物体的编号，存储n个物体中每个物体自己左邻右舍物体的编号（这两个邻居编号的顺序也是没有要求）。这样，输出的原理就从按盒内物体的前后顺序挨个输出，变为了先输出最头的物体，然后考察每个物体的左邻右舍是否被输出过，如果没有则输出。

不明白的话，举个例子。比如说，最后的结果是盒子1里有顺序为5,2,4,1,3，而计算机并不知道这个顺序，只知道盒子1里最头的是5，最尾的是3，以及每个物体相邻的左邻右舍。由于我们初始化存入左邻右舍next是所有元素都是0，所以一个物体 i 只有一个邻居时，可以是next[i][0]=0或者next[i][1]=0，而只有最头和最尾两个物体是这种情况。因此，从头开始，查找next[5]中除了0之外的另一个数，就是2，输出2并用flag数组标记。接着顺着查找next[2]，看2的两个邻居，肯定一个是5一个是4，这时考察flag数组的标记，就可以知道5已经被输出过了，4还没有，所以2的下一个是4...以此类推

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
	int m,n,t,flag[100006]={0}, next[100006][2]={0},head[100006]={0},end[100006]={0},num[100006]={0};
	scanf("%d %d",&n,&m);
	int i,j,x,y;
	for(i=1;i<=n;i++)//为了方便思考，n组数据我们选择从1到n而不是从0到n-1 
	{
		head[i]=i; end[i]=i; num[i]=1;//初始的时候是每个盒子里放着一个物品，是第几个盒子物品编号就是几 
	}
	for(i=0;i<m;i++)
	{
		scanf("%lld %lld",&x,&y);
		if(num[x]==0) continue;//每次输入的第一个盒子是空的的话，直接跳过了 
		else
		{
			if(num[y]==0)//如果第二个盒子是空的，直接倒着装进去就行了，很好理解
			{
				head[y]=end[x];
				end[y]=head[x];
			}
			else
			{
				if(next[head[x]][1]==0)      next[head[x]][1]=head[y]; //第一个盒子内的head物体只有一个邻居，所以看next中两个位置哪个空就把y的head物体放进去 
				else if(next[head[x]][0]==0) next[head[x]][0]=head[y];
				if(next[head[y]][1]==0)      next[head[y]][1]=head[x];//同理，给x的head配上邻居，也得对y进行同样的操作 
				else if(next[head[y]][0]==0) next[head[y]][0]=head[x];
				head[y]=end[x];// 第二个盒子新的head就是第一个盒子原来的end 
			}
			num[y]+=num[x];//别忘更新物体数量 
		    head[x]=0;//第一个盒子就空了 
		    end[x]=0;
		    num[x]=0;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(num[i]==0) printf("0\n");
		else
		{
			printf("%d",num[i]);
			printf(" %d",head[i]);
			flag[head[i]]=1;//用flag数组存储数据是不是输出过了，输出过了设为1 
			t=head[i];
			for(j=1;j<num[i];j++)
			{
				if(next[t][0]!=0&&flag[next[t][0]]!=1) 
				{
					printf(" %d",next[t][0]);
					t=next[t][0];
					flag[t]=1;
				}
				if(next[t][1]!=0&&flag[next[t][1]]!=1)
				{
					printf(" %d",next[t][1]);
					t=next[t][1];
					flag[t]=1;
				}
			}
			printf("\n");
		}
	}
	return 0;
}