10pts求调
查看原帖
10pts求调
539133
q1uple楼主2023/2/14 13:20
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
struct node{
	int to,nxt;
}g[M];
int h[M],cnt=0,inn[M],ans[M],k=0;
int n,m;
void add(int a,int b)
{
	g[++cnt].to=b;
	g[cnt].nxt=h[a];
	h[a]=cnt;
	inn[b]++;
}

void topsort()
{
	priority_queue<int>qq;
	for(int i=1;i<=n;i++)
	{
		if(inn[i]==0)
		{
			qq.push(i);
		} 	
	}
	while(!qq.empty())
	{
		int u=qq.top();
		qq.pop();
		ans[++k]=u;
		for(int i=h[u];i!=0;i=g[i].nxt)
		{
			int v=g[i].to;
			inn[v]--;
			if(inn[v]==0)
				qq.push(i);
		}
	}
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		memset(g,0,sizeof(g));
		memset(h,0,sizeof(h));
		memset(inn,0,sizeof(h)); 
		memset(ans,0,sizeof(ans));
		cnt=0,k=0;
		for(int i=1;i<=m;i++)
		{
			int a,b;
			cin>>a>>b;
			add(b,a);		
		}
		topsort();
		if(k>=n)
		{
			for(int i=n;i>=1;i--)
				cout<<ans[i]<<" ";
			printf("\n");
		}
		else
			printf("Impossible!\n");
	}
} 

QAQ

2023/2/14 13:20
加载中...