求解,离谱的蜜汁WA567点
查看原帖
求解,离谱的蜜汁WA567点
94726
萧道成楼主2021/7/18 16:53
#define N 100001
#define ll long long
using namespace std;
priority_queue<ll> q;
ll xian[N],hou[N],d[N],first[N],g[N],tot,next[N],vis[N];
ll shitian[N],go[N],ver[N],deg[N],head[N];
ll jc[N];
ll a[N],cnt=0;
void add(long long x,long long y)
{
	ver[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
	deg[y]++;
}
void topsort(ll n)
{
	for(ll i=1;i<=n;i++)
	{
	if(!deg[i])
	{
	q.push(i);
	vis[i]=1;
	}
	}
	while(q.size())
	{
	ll x=q.top();
	q.pop();
	a[++cnt]=x;
	for(ll i=head[x];i;i=next[i])
	{
	ll y=ver[i];
	if(vis[y])
	continue;
	deg[y]--;
	if(!deg[y])
	{
	q.push(y);
	vis[y]=1;
	}
	}
	}
	
	
	
	//return a[gg];
}
int main()
{
	freopen("P3243_7.in","r",stdin);
//	freopen("dictionary.out","w",stdout);
    ll T;
	cin>>T;
	while(T--)
	{
	ll n,m;
	memset(xian,0,sizeof(xian));
	memset(hou,0,sizeof(hou));
	memset(go,0,sizeof(go));
	memset(d,0,sizeof(d));
	memset(jc,0,sizeof(jc));
	memset(deg,0,sizeof(deg));
	memset(next,0,sizeof(xian));
	memset(head,0,sizeof(first));
	memset(vis,0,sizeof(vis));
	memset(a,0,sizeof(a));
	cnt=0;
	cin>>n>>m;
	for(ll i=1;i<=m;i++)
	{
	ll cha,ru;
	cin>>cha>>ru;
	add(ru,cha);
	jc[cha]=1;
	jc[ru]=1;
	//add(hou[i],xian[i]);
    }
    //for(ll r=1;r<=n;r++)
    //{
    //if(jc[r]==0)
    //add(r,r+1);
    //}
	topsort(n);
	if(cnt<n)
	{
	cout<<"Impossible!"<<endl;
	}
	if(n==cnt)
	for(ll o=cnt;o>=1;o--)
	cout<<a[o]<<" ";
	cout<<endl;
}
	return 0;
}
//这玩意儿交上去有时候WA五六七,有时候WA第七点,是发生甚么事了
2021/7/18 16:53
加载中...