Codeforces 404C Restore Graph

题目链接：http://codeforces.com/problemset/problem/404/C

题意：一个图有n个点，每一个点最多链接m条直线，给出所有点到顶点的距离(没有环)，输出所有直接相连的点

思路：构造，0距离的为顶点，1距离的接在0距离后面，2距离的接在1距离的后面，用了栈保存可以链接的点，如果栈空了构造失败，输出-1，有多个顶点或者没有顶点同样输出-1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define maxn 100030
using namespace std;

stack<int>dis[maxn];
int vis[maxn],ans_l[maxn],ans_r[maxn];

struct Node
{
    int val,pos;
}s[maxn];

bool cmp(Node p,Node q)
{
    return p.val<q.val;
}


int main()
{
    int n,k;
    while (scanf("%d%d",&n,&k)!=EOF)
    {
        int flag=1;
        memset(vis,0,sizeof(vis));
        for (int i=0;i<n;i++)
        {
            scanf("%d",&s[i].val);
            s[i].pos=i+1;
        }

        sort(s,s+n,cmp);
        dis[s[0].val].push(s[0].pos);
        for (int i=1;i<n;i++)
        {
            if (s[i].val==0 || dis[s[i].val-1].size()==0 || s[0].val!=0)
            {
                flag=0;
                break;
            }
            else if (dis[s[i].val-1].size()!=0)
            {
                int t=dis[s[i].val-1].top();
                ans_l[i]=t;
                ans_r[i]=s[i].pos;
                vis[t]++;
                vis[s[i].pos]++;
                if (vis[t]>=k) dis[s[i].val-1].pop();
                dis[s[i].val].push(s[i].pos);
                if (vis[s[i].pos]>=k) dis[s[i].val].pop();

            }
        }
        if (flag)
        {
            printf("%d\n",n-1);
            for (int i=1;i<n;i++)
             printf("%d %d\n",ans_l[i],ans_r[i]);
        }
        else
        {
            printf("-1\n");
        }
    }
}