USACO DEC09 Dizzy Cows

题目的大意就是确定输入的无向边的方向，使得所有无向边加入后依然是一个有向无环图。

思路很直接，先把所有的有向边加入图中，运行一次拓扑排序。如果不能排序，那么原图就有环，输出“-1” 并退出。然后，读入每条无向边(a,b)，若在拓扑序列中a在b前面，则方向为a指向b，否则为b指向a。

由于有多个解，USACO只给了输入数据，没有给输出数据。故本人增加了一个函数check，用于检查程序输出是否正确。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100010

typedef struct node
{
   long v;
   struct node *next;
}node;

long in[MAXN] = {};  //入度
long Q[MAXN];
long N,M,K;
node space[MAXN];
long empty = 0;
node *first[MAXN];

long pos[MAXN];   //点在拓扑序中的位置

void init()
{
   scanf("%ld%ld%ld\n",&N,&M,&K);
   long i,a,b;
   for(i = 0;i < M;i ++)
   {
       scanf("%ld%ld\n",&a,&b);
       space[empty].v = b;
       space[empty].next = first[a];
       first[a] = space + empty;
       empty ++;
       in[b] ++;
   }
}

void toposort()
{
   node *p;
   long i,head,tail;
   head = tail = 0;
   for(i = 1;i <= N;i ++)
       if(in[i] == 0)    Q[tail ++] = i;
   while(head < tail)
   {
       i = Q[head ++];
       for(p = first[i];p != NULL;p = p->next)
       {
           in[p->v] --;
           if(in[p->v] == 0)
               Q[tail ++] = p->v;
       }
   }
   if(tail < N)
   {
       printf("-1\n");
       exit(0);
   }
   for(i = 0;i < tail;i ++)
       pos[Q[i]] = i;
}

void add(long a,long b)   //用于测试
{
   node *p = malloc(sizeof(node));
   p->v = b;
   p->next = first[a];
   first[a] = p;
}

void check()   //用于测试
{
   node *p;
   int i,head,tail;
   memset(in,0,sizeof(in));
   for(i = 1;i <= N;i ++)
       for(p = first[i];p != NULL;p = p->next)
           in[p->v] ++;
   head = tail = 0;
   for(i = 1;i <= N;i ++)
       if(in[i] == 0)    Q[tail ++] = i;
   while(head < tail)
   {
       i = Q[head ++];
       for(p = first[i];p != NULL;p = p->next)
       {
           in[p->v] --;
           if(in[p->v] == 0)
               Q[tail ++] = p->v;
       }
   }
   if(head == N && tail == N)    fprintf(stderr,"Correct!\n");
   else    fprintf(stderr,"Wrong!\n");
}

void arrange()
{
   long i,a,b;
   for(i = 0;i < K;i ++)
   {
       scanf("%ld%ld",&a,&b);
       if(pos[a] < pos[b])
       {
           printf("%ld %ld\n",a,b);
           add(a,b);
       }
       else
       {
           printf("%ld %ld\n",b,a);
           add(b,a);
       }
   }
}

int main()
{
   freopen("dizzy.in","r",stdin);
   freopen("dizzy.out","w",stdout);
   init();
   toposort();
   arrange();
   check();
   fclose(stdin);
   fclose(stdout);
   return 0;
}