Original link: https://blog.chungzh.cn/articles/cf-1385e/
CF-1385E Directing Edges
meaning of the title
Given a graph consisting of directed and undirected edges, you now need to turn all undirected edges into directed edges such that the resulting graph has no cycles .
If it can be done, please output the figure, otherwise output “NO” directly.
analyze
We first connect only directed edges, and then do a topological sort. If it fails, it means there is a cycle, and output “NO”.
Then process the remaining undirected edges. For an undirected edge $(u, v)$, if the topological order of $u$ is less than $v$, then let the direction of this edge be $u\rightarrow v$. Otherwise, the direction is $v\rightarrow u$. Because this edge is from a point with a small topological order to a point with a large topological order, it must not form a ring.
RECORD
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std ; const int MAXN = 200005 ; int n , m ; vector < int > G [ MAXN ]; int c [ MAXN ], topo [ MAXN ], id [ MAXN ], t , bn , x [ MAXN ], y [ MAXN ]; bool dfs ( int u ) { c [ u ] = - 1 ; for ( auto v : G [ u ]) { if ( c [ v ] < 0 ) return false ; else if ( c [ v ] == 0 && ! dfs ( v )) return false ; } c [ u ] = 1 ; topo [ -- t ] = u ; id [ u ] = t ; return true ; } bool toposort () { t = n ; memset ( c , 0 , sizeof ( c )); memset ( id , 0 , sizeof ( id )); memset ( topo , 0 , sizeof ( topo )); for ( int i = 1 ; i <= n ; i ++ ) if ( ! c [ i ]) if ( ! dfs ( i )) return false ; return true ; } int main () { ios :: sync_with_stdio ( false ); int t ; cin >> t ; while ( t -- ) { cin >> n >> m ; for ( int i = 1 ; i <= n ; i ++ ) G [ i ]. clear (); bn = 0 ; for ( int i = 0 ; i < m ; i ++ ) { int ti , tx , ty ; cin >> ti >> tx >> ty ; if ( ti == 0 ) { // 无向x [ ++ bn ] = tx ; y [ bn ] = ty ; } else { G [ tx ]. push_back ( ty ); } } if ( ! toposort ()) { cout << "NO \n " ; continue ; } cout << "YES \n " ; for ( int i = 1 ; i <= bn ; i ++ ) { if ( id [ x [ i ]] <= id [ y [ i ]]) cout << x [ i ] << " " << y [ i ] << endl ; else cout << y [ i ] << " " << x [ i ] << endl ; } for ( int i = 1 ; i <= n ; i ++ ) { for ( auto j : G [ i ]) { cout << i << " " << j << endl ; } } } return 0 ; }
|
This article is reproduced from: https://blog.chungzh.cn/articles/cf-1385e/
This site is for inclusion only, and the copyright belongs to the original author.