HDU 5813 Elegant Construction ——（拓扑排序，构造）

　　可以直接见这个博客：http://blog.csdn.net/black_miracle/article/details/52164974。

　　对其中的几点作一些解释：

　　1.这个方法我们对队列中取出的元素，把仍有出度的点连接到这个点时，这个点是不会连接到多余的点的，因为：一个点出队列的时候其他没入队的点都已经连接到这个点过了，后来再一个点出队列的时候，我们拿此时没入队的点连接到它时，肯定已经连接过之前的点了，所以肯定不会增加到达的点数。（可能我也用语言讲不太清楚233。。。）

　　2.为什么这个人的博客说最终如果num不是0的话就表示成环了？理由如下：不妨考虑四个点的情况：3，3，3，0。最后一个点操作后，出度变为2，2，2，0。这个时候队列已经空了，然而num还不是0，说明还有点没有完成达到它所需要达到的点数（也可以这么解释：num的个数表示还没有完成点数个数任务的点的个数，num=0才表示所有的点都已经完成到达点数个数的目标了，不是0当然不能够满足题意了）。至于为什么是成环的话，因为它们不能够完成点数个数任务，所以他们必须连向别人构成环来构成目标了呗~

　　反正这个拓扑排序有点奥义，需要好好理解~

　　代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int N = 1000 + 5;

struct edge
{
    int u,v;
    bool operator < (const edge &temp) const
    {
        return u == temp.u ? v<temp.v : u<temp.u;
    }
};
int a[N],inq[N],n;
set<edge> S;

void solve()
{
    queue<int> Q;
    int cnt = n;
    for(int i=1;i<=n;i++)
    {
        if(!a[i])
        {
            Q.push(i);
            inq[i] = 1;
            cnt--;
        }
    }
    while(!Q.empty())
    {
        int x = Q.front();Q.pop();
        for(int i=1;i<=n;i++)
        {
            if(!inq[i])
            {
                a[i]--;
                S.insert((edge){i,x});
                if(!a[i])
                {
                    Q.push(i);
                    inq[i] = 1;
                    cnt--;
                }
            }
        }
    }
    if(cnt) puts("No");
    else
    {
        puts("Yes");
        printf("%d
",S.size());
        for(set<edge>::iterator it=S.begin();it!=S.end();it++)
        {
            edge e = *it;
            printf("%d %d
",e.u,e.v);
        }
    }
}

int main()
{
    int T;scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        scanf("%d",&n);
        S.clear();memset(inq,0,sizeof(inq));
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        printf("Case #%d: ",kase);
        solve();
    }
    return 0;
}