1 条题解

  • 0
    @ 2026-4-17 20:42:02
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    vector<int>G[N];deque<int>ans;int v[N],rd[N],cd[N],cnt;set<int>s;
    void solve()
    {
    	memset(G,0,sizeof(G));ans.clear();memset(v,0,sizeof(v)),memset(rd,0,sizeof(rd)),cnt=0,s.clear();
    	int n,m;cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{
    		int x,y;cin>>x>>y;
    		G[y].push_back(x);
    		rd[x]++;
    	}
    	priority_queue<int>q;
    	for(int i=1;i<=n;i++)if(rd[i]==0)q.push(i);
    	while(!q.empty())
    	{
    		int x=q.top();q.pop();v[x]=1;ans.push_front(x);
    		for(int y:G[x])
    		{
    			rd[y]--;
    			if(rd[y]==0)q.push(y);
    		}
    	}
    	if(ans.size()!=n)
    	{
    		cout<<"Impossible!\n";
    		return;
    	}
    	for(int y:ans)cout<<y<<" ";cout<<'\n';
    }
    int main()
    {
    	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    	int t;cin>>t;
    	while(t--)solve();
    	return 0;
    }
    
    • 1

    信息

    ID
    5675
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    28
    已通过
    11
    上传者