想的时间比较长所以看题解了= =

原题：

Fj有N（N<=1000）头牛，每头牛都有独一无二的正整数 魅力值，Fj想让他们按

魅力值排序。

Fj已经知道M（1<=M<=10000）对奶牛的魅力值，但他发现，他还需要再做一张关

于另外C对奶牛的魅力值比较，才能推断出所有奶牛的魅力值的顺序。

现在请你帮他 算出最小的C值。

 

刚在拓扑排序方向上想，思路是每次选一个入度为0的点，让这个点向其它所有入度为0的点连边，然后这个点就是目前最高点了，然后就可以删掉不管了，所以可以直接删掉这个点

为了保证最坏情况所以每次删掉的点是所有入度为0的点中从这个点出发能到达的点最多的点

然后用堆搞一下，发现答案不对？

手玩小数据没问题，想了将近一下午无果，遵循经很多神犇"想的时间太长就不要再想"的建议，选择看题解

正解是用减法原理，确定完整的关系需要知道n*(n-1)/2条关系，已知的关系就是每个点能到达的点的个数的和，dfs搞一搞就可以了

然后遇到两个小问题，就是下面这两个dfs都是不对的：

/*void dfs(int x){注意这样可能会有重复的	f[x]=1;	for(int i=LINK[x];i;i=e[i].next){		if(!f[e[i].y])  dfs(e[i].y);		f[x]+=f[e[i].y];	}}*//*int dfs(int x){这样也可能会有重复的	int z=1;	for(int i=LINK[x];i;i=e[i].next)  z+=dfs(e[i].y);	return z;}*/

反例很简单，请自己手玩

代码（我直接在原来堆的错误写法上改的，有一个堆还有各种乱搞，所以代码比较长= =）：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int read(){
    int z=0,mark=1;  char ch=getchar(); 8     while(ch<'0'||ch>'9'){
    if(ch=='-')mark=-1;  ch=getchar();} 9     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}10     return z*mark;11 }12 struct ddd{
    int next,y;}e[11000];  int LINK[1100],ltop=0,rd[1100],cd[1100];13 inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;cd[x]++;rd[y]++;}14 int n,m;15 //int QUEUE[1100000],head=0;16 int ans=0;17 bool flag[1100];18 int f[1100];19 int visited[1100];20 int max_heap[1100],size=0;21 void push(int x){22     max_heap[size]=x;23     int current=size,father=(size-1)>>1;24     while(f[max_heap[current]]>f[max_heap[father]] && father>=0){25         swap(max_heap[current],max_heap[father]);26         current=father,father=(current-1)>>1;27     }28     size++;29 }30 void updata(int x){31     int lchild=(x<<1)+1,rchild=(x<<1)+2;32     int max_id=x;33     if(lchild
           
            f[max_heap[max_id]]) max_id=lchild;34 if(rchild
            
             f[max_heap[max_id]]) max_id=rchild;35 if(max_id!=x){36 swap(max_heap[x],max_heap[max_id]);37 updata(max_id);38 }39 }40 void pop(){41 swap(max_heap[0],max_heap[size-1]);42 size--;43 updata(0);44 }45 /*void dfs(int x){注意这样可能会有重复的：(1,2),(3,2)46 f[x]=1;47 for(int i=LINK[x];i;i=e[i].next){48 if(!f[e[i].y]) dfs(e[i].y);49 f[x]+=f[e[i].y];50 }51 }*/52 /*int dfs(int x){这样也可能会有重复的，比如(1,2),(2,3),(1,3)53 int z=1;54 for(int i=LINK[x];i;i=e[i].next) z+=dfs(e[i].y);55 return z;56 }*/57 int dfs(int x,int y){58 int z=1;59 for(int i=LINK[x];i;i=e[i].next)if(visited[e[i].y]!=y){60 visited[e[i].y]=y;61 z+=dfs(e[i].y,y);62 }63 return z;64 }65 int main(){ //freopen("ddd.in","r",stdin);66 memset(flag,0,sizeof(flag));67 cin>>n>>m;68 int _left,_right;69 while(m --> 0){ //趋向于70 _left=read(),_right=read();71 insert(_left,_right);72 }73 //for(int i=1;i<=n;++i)if(!rd[i]) QUEUE[++head]=i,++cnt;74 for(int i=1;i<=n;++i) ans+=dfs(i,i)-1;75 //for(int i=1;i<=n;++i)if(!rd[i]) push(i);76 /*for(int i=1;i<=n;++i){77 cout<
             
              <