【构造+拓扑排序】CF1385E

r囧r小猫 2024-03-17 11:37 65阅读 0赞

[Problem - 1385E - Codeforces][]

题意：

![e5bb03d5f2804bc7871a58b507e1dcca.png][]

![4249d8f58b254890a4c8748cff33daf3.png][]

思路：

给无向边标方向，构造的条件是没有环

那么特殊情况就是按拓扑序的反序标方向即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    
    queue<int> q;
    vector<pair<int,int> > V;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,M,tot=0,idx=0,cnt=0;
    int t,u,v;
    int head[mxn],in[mxn],In[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	V.clear();
    	while(!q.empty()) q.pop();
    	tot=0;idx=0;cnt=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    		in[i]=In[i]=0;
    	}
    }
    void topsort(){
    	for(int i=1;i<=N;i++){
    		if(!in[i]) q.push(i);
    	}
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		In[u]=++idx;
    		cnt++;
    		for(int i=head[u];~i;i=edge[i].next){
    			in[edge[i].to]--;
    			if(!in[edge[i].to]) q.push(edge[i].to);
    		}
    	}
    }
    void solve(){
    	cin>>N>>M;
    	G_init();
    	for(int i=1;i<=M;i++){
    		cin>>t>>u>>v;
    		if(t==1){
    			add(u,v);
    			in[v]++;
    		}else{
    			V.push_back({u,v});
    		}
    	}
    	topsort();
    	if(cnt<N){
    		cout<<"NO"<<'\n';
    		return;
    	}
    	cout<<"YES"<<'\n';
    	for(int u=1;u<=N;u++){
    		for(int i=head[u];~i;i=edge[i].next){
    			cout<<u<<" "<<edge[i].to<<'\n';
    		}
    	}
    	for(int i=0;i<V.size();i++){
    		if(In[V[i].first]<In[V[i].second]) cout<<V[i].first<<" "<<V[i].second<<'\n';
    		else cout<<V[i].second<<" "<<V[i].first<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 1385E - Codeforces]: https://codeforces.com/problemset/problem/1385/E
[e5bb03d5f2804bc7871a58b507e1dcca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/a42dedd144b9450dacfb84867a767347.png
[4249d8f58b254890a4c8748cff33daf3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/d6039d1d64dd400f834269e8c15d546d.png