1 条题解
-
1
SOLUTION
结论:反向连边,找字典序最大的拓扑序即为答案。
显然直接找字典序最小的假了,如 连边,答案
3 1 2,错解2 1 3。对于结论,我不会证,但是我找不到反例,我就认为他是对的了。
具体地,建反图,并用
std::priority_queue代替std::queue。CODE
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int T,n,m; map<pair<int,int>,int> mp; vector<int> G[101000]; int ind[101000]; priority_queue<int> pq; vector<int> vec; void topo(){ vec.clear(); for(int i=1;i<=n;i++){ if(!ind[i]) pq.push(i); } while(!pq.empty()){ int u=pq.top(); vec.push_back(u),pq.pop(); for(int v:G[u]){ if(!(--ind[v])) pq.push(v); } } if(vec.size()<n) cout<<"No Solution!"; else{ reverse(vec.begin(),vec.end()); for(int i:vec) cout<<i<<' '; } cout<<'\n'; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n>>m; for(int i=1;i<=n;i++){ G[i].clear(); ind[i]=0; } mp.clear(); for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; if(mp[{u,v}]) continue; mp[{u,v}]=1; G[v].push_back(u); ind[u]++; } topo(); } return 0; }
- 1
信息
- ID
- 439
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 65
- 已通过
- 16
- 上传者