题意：

约翰的N头牛排成一行挤奶时，有确定的顺序。他拥有L条关于奶牛顺序的信息，所有的信息都写成“A在B的前面”这样的形式。请帮助约翰删除尽可能多的冗余信息，但要保证能推出原有的顺序。n≤1500。

题解：

首先拓扑排序，并给每个节点设定一个bitset存储哪些点能到达此点。接着按边终点拓扑序升序为第一关键字，起点拓扑序降序为第二关键字依次插边，如果当前终点的bitset里起点不为1则该边保留，并将终点的bitset和起点的bitset合并，否则该边不保留。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define inc(i,j,k) for(int i=j;i<=k;i++) 7 #define maxn 1510 8 using namespace std; 9 10 inline int read(){11     char ch=getchar(); int f=1,x=0;12     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();14     return f*x;15 }16 struct e{
   int f,t,n;}es[maxn*100],es2[maxn*100]; int g[maxn],tot;17 void pe(int f,int t,int ess){es[ess]=(e){f,t,g[f]}; g[f]=ess;}18 int n,l,topo[maxn],du[maxn];19 bool cmp1(e a,e b){
   return topo[a.t]==topo[b.t]?topo[a.f]>topo[b.f]:topo[a.t]
          

q; bitset

f[maxn];22 int main(){23 n=read(); l=read(); inc(i,1,l){ int x=read(),y=read(); pe(x,y,i); du[y]++;} inc(i,1,n)if(!du[i])q.push(i);24 while(!q.empty()){25 int x=q.front(); q.pop();26 for(int i=g[x];i;i=es[i].n){27 du[es[i].t]--; if(!du[es[i].t])q.push(es[i].t),topo[es[i].t]=topo[x]+1;28 }29 }30 sort(es+1,es+l+1,cmp1); inc(i,1,n)f[i][i]=1;31 inc(i,1,l){ if(!f[es[i].t][es[i].f])es2[++tot]=es[i]; f[es[i].t]|=f[es[i].f];}32 sort(es2+1,es2+tot+1,cmp2); printf("%d\n",tot);33 inc(i,1,tot)printf("%d %d\n",es2[i].f,es2[i].t); return 0;34 }