10分求助
查看原帖
10分求助
544113
不慕放糖楼主2021/9/28 21:27
#include<bits/stdc++.h>
using namespace std;
vector<int>g[10000];
queue<int>q;
int in[10000],len=0,ok,n,m,ans[1000];

inline void clean()
{
    for(int i=1;i<=n;i++) in[i] = 0,ans[i]=0;
    len=0;
}

inline void tpsort(){
	for(int i=1;i<=n;i++){
		if(in[i]==0) q.push(i);
	}
	
	while(!q.empty()){
		int u=q.front(); ans[++len]=u; q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			in[v]--;
			if(in[v]==0) {
				q.push(v);
			}
		}
	}
	return;
}
int main(){
	int d;
	cin>>d;
	while(d--){
		cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		in[y]++;
	}
	tpsort();
	for(int j=1;j<=n;j++)
		if(in[j]!=0)
		   {
		   	ok=1;
		   	break;
		   }
	
	if(ok!=1){
		for(int i=1;i<=len;i++) cout<<ans[i]<<" ";
		cout<<endl;
	}
	else cout<<"Impossible!"<<endl;
	clean();
	}
	return 0;
} 
2021/9/28 21:27
加载中...