POJ #1033

First, 写POJ的报告用毛英文啊...

这道题思路不算难，主要参考了这里：http://www.cnblogs.com/damacheng/archive/2010/09/24/1833983.html 讲得很清楚，但是代码有点复杂，我个人觉得不需要：循环情况可以当作非循环的一个特殊情况，简单处理一下就可以了：临时cluster只保留最后一个要操作的cluster index，留在最后赋值(move)给最后一个cluster即可。这样就需要一个deque来把这个多余的操作放在栈底(push_front)。这个技巧可以大大简化代码逻辑。

另外还有个小技巧：判断一个cluster是否已经入栈，不需要一个单独的bool[]，只需要把cluster数组值取负就可以了，最后输出以后再取正。

最后，如果把deque放到function里面会有segment fault，而当作global variable就没有这个问题。也就是说局部栈空间比全局栈空间要小。

奇怪的是POJ过了，但是ZOJ是WA：

//    1033
//    http://www.cnblogs.com/damacheng/archive/2010/09/24/1833983.html

#include <stdio.h>
#include <stdlib.h>
#include <deque> 
using namespace std;

#define MAX_N 10020
deque<int> ops;        // OJ style. Global stack is larger. Or, SegFault

//    Disjoint cycles, clojure
int find_tmp(int n, int *cluster)
{
    for (int i = n; i > 1; i--)
    {
        if (cluster[i] == 0) return i;
    }
}

void calc(int n, int *cluster)
{
    int mvCnt = 0;
    for (int c = 1; c <= n; c++)
    {
        if (c == cluster[c] || cluster[c] == 0) continue;

        ops.clear();

        //    Pushing
        int n_c = c;
        int n_val = cluster[c];
        int tmp = -1;
        while (n_val != 0)
        {
            //    Is it cyclic?
            if (cluster[n_val] < 0)
            {
                tmp = find_tmp(n, cluster);
                
                ops.push_back(n_c);
                
                cluster[tmp] = -cluster[n_c];    
                cluster[n_c] = -tmp;            
                
                ops.push_front(tmp);

                break;
            }

            //    In stack and mark
            ops.push_back(n_c);
            cluster[n_c] *= -1;

            //    Move to next
            n_c = n_val;
            n_val = cluster[n_val];
        }

        //    Popping for move
        while (!ops.empty())
        {
            int cc = ops.back();            
            cluster[cc] *= -1;

            //    Move
            printf("%d %d
", cc, cluster[cc]);
            mvCnt++;

            if (cluster[cc] != tmp)    // the tmp bin is special
            {
                cluster[cluster[cc]] = cluster[cc];
            }
            cluster[cc] = 0;
            ops.pop_back();
        }
    }

    if (mvCnt == 0)
    {
        printf("No optimization needed
");
    }
}

int main()
{
    int n, k;
    int cluster[MAX_N] = { 0 };

    //    Input    
    int cnt = 1;
    scanf("%d%d", &n, &k);
    
    for (int i = 0; i < k; i++)
    {
        int currN = 0;    scanf("%d", &currN);
        for (int j = 0; j < currN; j++)
        {
            int currInx = 0; scanf("%d", &currInx);
            cluster[currInx] = cnt++;
        }
    }

    calc(n, cluster);
        
    return 0;
}