stack（hdu）

题意：有n个栈，第i个栈刚开始只放了i，有m个操作，每次把ai放到bi里，求最后每个栈里元素的个数和元素

模拟肯会超时，那么我们就想用双链表来写

s数组用来存一个数的前面相连的数或者后面的数（因为堆的话一个数只能连两个数）

struct name{
	int pre,next;
}s[N];

sta数组用来记录栈顶和栈底元素

struct po{
	int top,bot;
}sta[N];

f数组来记录这个数输出过没有，num来记录每个栈的元素的个数

int f[N],num[N];

刚开始初始化的时候每个栈的栈顶和栈底都是i本身，然后num都是1，f初始化为0，每个数没有与他相连的数，所以前面后面都是0

for(int i=1;i<=n;i++){
			num[i]=1;
			sta[i].top =sta[i].bot =i;
			f[i]=0;
			s[i].next =s[i].pre =0;
		}

然后我们对于把a这个栈放到b这个栈的add操作：

我们分别用xyzq来记录a的栈顶和栈底，b的栈顶和栈底

把a放入b，那么a的栈底就是b的栈顶

a的num要加到b的num里去，a的num变成0

然后a的栈顶x就会连上b的栈顶z，判断一下x有没有与他相连的数

如果没有就把z连到x的后面next，如果有就连到x的前面pre

z的情况也是一样，如果z后面没有的话就连到后面，有的话就连到前面

#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<list>
#include<map>
#include<cstdio>
typedef long long ll;
typedef int64_t s64;
using namespace std;
struct node{
    int pre,next;
}s[200005];
struct stac{
    int top,bot;
}sta[200005];
int num[200005];
void add(int a,int b){
    int x=sta[a].top;
    int y=sta[a].bot;
    int z=sta[b].top;
    int q=sta[b].bot;
    if(!num[b]){        //b栈中没有东西
        sta[b].bot=x;   //a的头变b的底
        sta[b].top=y;   //a的底比b的头
        sta[a].top=sta[a].bot=0; //把a头和底置0 
    }
    else{              //b栈有东西
        if(!s[x].next){   //判断a栈中的头是否是next空（因为此题为双向链表不能确定是next还是pre）
            s[x].next=z;
        }   
        else{   //判断a栈中的头是否是pre空
            s[x].pre=z;
        }
        if(!s[z].next){   //判断b栈中的头是否是next空（双向链表所以a和b是需要相互连接的）
            s[z].next=x;
        }
        else{   //判断b栈中的头是否是pre空
            s[z].pre=x;
        }   //在这之前都是在做将ab栈连接起来的操作
        sta[b].top=y;   //把a的底变b的头
        sta[a].top=sta[a].bot=0;   //把a的头和底置0
    }
    num[b]+=num[a];
    num[a]=0;
}
int sig[200005];
int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){   //初始化n个栈
            s[i].pre=s[i].next=0;
            sta[i].top=sta[i].bot=i;
            num[i]=1;
            sig[i]=0;
        }
        int x,y;
        while(m--){
            cin>>x>>y;
            if(num[x]==0)
                continue;
            add(x,y);
        }
        for(int i=1;i<=n;i++){
            int k=sta[i].top;
            cout<<num[i];   //输出当前栈中的数据个数
            if(num[i]){     //判断是否栈中有数据   
                while(k){
                    cout<<" "<<k;   
                    sig[k]=1;   //每次找到并且输出后都需要标记
                    if(s[k].next&&sig[s[k].next]!=1){   //寻找下一个数据，因不确定是next还是pre所以需要进行以下的判断
                        k=s[k].next;
                    }
                    else if(s[k].pre&&sig[s[k].pre]!=1){
                        k=s[k].pre;
                    }
                    else{
                        k=0;   //找不到下一个退出循环
                    }
                }
            }
            cout<<endl;
        }
    }
    return 0;
}