记录编号	521822	评测结果	AAAAAAAAAA
题目名称	[USACO Open18 Gold] Milking Order	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.797 s
提交时间	2018-11-07 21:26:33	内存使用	5.66 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
inline int read(){
    int x=0,fz=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')fz=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*fz;
}
priority_queue<int>q;
vector<int>b[100010],s[50010];
int n,m,l1=1,r1,ans,a1,x[50010],r[100010];
bool bk[100010];
inline void addb(int p){
    for(int i=1;i<=n;i++)b[i].clear(),r[i]=bk[i]=0;
    for(int i=1;i<=p;i++){
	    if(x[i]!=1)for(int j=0;j<x[i]-1;j++){
		    b[s[i][j]].push_back(s[i][j+1]);
		    r[s[i][j+1]]++;
		}
	}
	return;
}
inline void dfs(int p){bk[p]=1;
    if(b[p].size())for(int i=0;i<b[p].size();i++){
	    r[b[p][i]]--;
	    if(!r[b[p][i]]&&!bk[b[p][i]])dfs(b[p][i]);
	}
}
inline int ju(){
    for(int i=1;i<=n;i++)if(!bk[i]&&!r[i])dfs(i);
    for(int i=1;i<=n;i++)if(!bk[i])return 0;
    return 1;
}
int MAIN(){
	freopen("milkorder_gold_18open.in","r",stdin);
	freopen("milkorder_gold_18open.out","w",stdout);
    n=read();m=read();r1=m;
    for(int i=1;i<=m;i++){
	    x[i]=read();
	    for(int j=1;j<=x[i];j++){
		    a1=read();
		    s[i].push_back(a1);
		}
	}
	while(l1<=r1){
	    int mid=(l1+r1)>>1;
	    addb(mid);
	    if(ju())ans=mid,l1=mid+1;
	    else r1=mid-1; 
	}
	addb(ans);
	for(int i=1;i<=n;i++)if(!r[i])q.push(-i);
	while(q.size()){
	    a1=-q.top();q.pop();printf("%d ",a1);
	    if(b[a1].size())for(int i=0;i<b[a1].size();i++){
		    r[b[a1][i]]--;
		    if(!r[b[a1][i]])q.push(-b[a1][i]);
		}
	}
	return 0;
}
int pp=MAIN();
int main(){;}