topsort
被拓扑排序给安排了
这道题让我们给边加方向让,最终的图没有环。
其实没有环就意味着他是一个DAG所以他一定有一个拓扑序
这点我是想到了
但是,思维能力不够。我做响了错误的方向。把这道题做的极其困难。
我们可以先并不关心没有方向的边。我们先处理有方向的边。
将有方向的边建一个拓扑序。然后让我方向的边遵照这个拓扑序进行方向的选定就好了!!!!
真的是太妙了。因为我不熟悉拓扑排序所以没有想到。
虽说是套路题,但是我觉得是好题!!
#include<iostream> #include<algorithm> #include<vector> #include<deque> using namespace std; typedef pair<int,int> pii; const int max_n = 2e5+100; vector<int> G[max_n]; int n,m; int ts[max_n]; int ru[max_n]; bool topsort(){ deque<int> que; for (int i=1;i<=n;++i)if (ru[i]==0)que.push_back(i); int st=0; while(!que.empty()){ int u = que.front();que.pop_front(); ts[u]=++st; for (int v:G[u]){ --ru[v]; if (ru[v]==0)que.push_back(v); } }return st==n; } int main(){ int t;cin>>t; while(t--){ vector<int> tps; vector<pii> es; cin>>n>>m; for (int i=0;i<=n+10;++i)G[i].clear(),ru[i]=0; for (int i=1,ty,u,v;i<=m;++i){ cin>>ty>>u>>v; if (ty==1)G[u].push_back(v),ru[v]++; else es.push_back(pii(u,v)); } if (!topsort()){ cout<<"NO\n"; continue; } cout<<"YES\n"; for (int i=1;i<=n;++i)for (int v:G[i])cout<<i<<" "<<v<<endl; for (pii p : es){ if (ts[p.first]>ts[p.second])swap(p.first,p.second); cout<<p.first<<" "<<p.second<<endl; } } }