记录编号	551062	评测结果	AAAAAAAAAA
题目名称	3390.[USACO20 Open Silver]Cereal	最终得分	100
用户昵称	魔笛	是否通过	通过
代码语言	C++	运行时间	1.609 s
提交时间	2020-04-06 17:32:51	内存使用	15.18 MiB

#include <cstdio>
#include<iostream> 
using namespace std;
int n,m,cnt,n1[100010],n2[100010],bel[100010],ans[100010];
void search(int x,int y){
    if(!bel[y]){
        bel[y]=x; 
        cnt++;
    }else if(bel[y]>x){ //被编号大的牛拿走
        int tmp=bel[y];
        bel[y]=x;
        if(y==n1[tmp]) 
		   search(tmp, n2[tmp]);
    }
}
int main() {
    freopen("usaco_20Open_cereal.in","r",stdin);
    freopen("usaco_20Open_cereal.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>n1[i]>>n2[i];
    for(int i=n;i>0;i--){
        search(i,n1[i]);
        ans[i-1]=cnt;
    }
    for(int i=0;i<n;i++) cout<<ans[i]<<endl;
    return 0;
}