poj 1033 defragment

簇移动问题，用到栈

#include<stdio.h>
#include<stack>
using namespace std;
#define MAX 10000
int clusters[MAX+10];
int main()
{int N,K;while(scanf("%d%d",&N,&K)!=EOF){stack<int> s;int i,j,m=0,n;for(i=1;i<=N;i++)clusters[i]=0;for(i=1;i<=K;i++){int s;scanf("%d",&s);for(j=1;j<=s;j++){scanf("%d",&n);clusters[n]=++m;     \\簇n本来该在的位置}}int next,movenum=0;for(i=1;i<=N;i++){if(clusters[i]==i)        \\不用移动continue;else if(clusters[i]!=0)     \\为0不用管，不为0时进入讨论{s.push(i);next=clusters[i];bool is_circle;while(true){if(clusters[next]==0){is_circle=false;  \\没有形成环，后面的直接往前面空簇移动就行break;}else if(clusters[next]==i){is_circle=true;     \\形成了环break;}else{s.push(next);next=clusters[next];}}if(is_circle){int move;for(j=N;j>=1;j--)   \\从最后面开始找空簇，用来放形成环的第一个簇if(clusters[j]==0)break;printf("%d %d\n",next,j);clusters[j]=clusters[next];     \\先移动过去while(!s.empty())     \\此时是非环的情况了，则按链来处理，一个个往前移动{move=s.top();printf("%d %d\n",move,next);clusters[next]=clusters[move];next=move;s.pop();movenum++;}printf("%d %d\n",j,next);  \\移动完了，把最后的往初始位置放clusters[next]=clusters[j];clusters[j]=0;     \\移动完的位置置0，表示空簇}else{int move;while(!s.empty()){move=s.top();printf("%d %d\n",move,next);clusters[next]=clusters[move];next=move;s.pop();movenum++;}clusters[next]=0;  \\链情况下，移动完的位置置0}}}if(movenum==0)   \\没有经过任何移动printf("No optimization needed\n");}return 0;
}