fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> ii;
  4.  
  5. const int NAX = 200002;
  6. const int MAX = 1e9+2;
  7.  
  8. vector<vector<int> > adj(NAX), adj_rev(NAX);
  9. vector<bool> used(NAX);
  10. vector<int> order, component;
  11. vector<int> root_nodes;
  12. vector<int> roots(NAX);
  13. vector<vector<int> > adj_scc(NAX);
  14.  
  15. void dfs1(int v) {
  16.     used[v] = true;
  17.     for (auto u : adj[v])
  18.         if (!used[u])
  19.             dfs1(u);
  20.  
  21.     order.push_back(v);
  22. }
  23.  
  24. void dfs2(int v) {
  25.     used[v] = true;
  26.     component.push_back(v);
  27.  
  28.     for (auto u : adj_rev[v])
  29.         if (!used[u])
  30.             dfs2(u);
  31. }
  32.  
  33. bool cando(int mid, vector<tuple<int,int,int> > &edges, int n){
  34. 	order.clear();
  35. 	root_nodes.clear();
  36. 	for (int i=1; i<=n; i++) adj[i].clear(), adj_rev[i].clear(), adj_scc[i].clear(); // roots[i]=0
  37.  
  38. 	for (int i=0; i<edges.size(); i++){
  39. 		int u=get<0>(edges[i]);
  40. 		int v=get<1>(edges[i]);
  41. 		int w=get<2>(edges[i]);
  42. 		adj[u].push_back(v);
  43. 		adj_rev[v].push_back(u);
  44. 		if (w<=mid){
  45. 			adj[v].push_back(u);
  46. 			adj_rev[u].push_back(v);
  47. 		}
  48. 	}
  49.  
  50. 	for (int i=1; i<=n; i++) used[i]=false;
  51. 	for (int i=1; i<=n; i++)
  52.         if (!used[i])
  53.             dfs1(i);
  54.  
  55.     for (int i=1; i<=n; i++) used[i]=false;
  56.     reverse(order.begin(), order.end());
  57.  
  58.     for (auto v : order)
  59.         if (!used[v]) {
  60.             dfs2 (v);
  61.  
  62. 			int root = component.front();
  63. 			for (auto u : component) roots[u] = root;
  64. 			root_nodes.push_back(root);
  65.  
  66.             component.clear();
  67.         }
  68.  
  69.     vector<int> indeg(n+1,-1);
  70.     for (int i=0; i<root_nodes.size(); i++) indeg[root_nodes[i]]=0;
  71.     for (int v = 1; v <= n; v++)
  72.     for (auto u : adj[v]) {
  73.         int root_v = roots[v],
  74.             root_u = roots[u];
  75.  
  76.         if (root_u != root_v){
  77.         	adj_scc[root_v].push_back(root_u);
  78.         	indeg[root_u]++;
  79.         }
  80.     }
  81.  
  82.  
  83.     queue<int> bfs;
  84.     for (int i=1; i<=n; i++) used[i]=false;
  85.     for (int i=1; i<=n; i++){
  86.     	if (indeg[i]==0){
  87.     		bfs.push(i);
  88.     		used[i]=true;
  89.     	}
  90.     }
  91.     if (bfs.size()>1){
  92.     	//cout<<123<<endl;
  93.     	return false;
  94.     }
  95.     while(!bfs.empty()){
  96.     	int u = bfs.front();
  97.     	bfs.pop();
  98.     	for (int i=0; i<adj_scc[u].size(); i++){
  99.     		int v=adj_scc[u][i];
  100.     		if (!used[v]){
  101.     			used[v]=true;
  102.     			bfs.push(v);
  103.     		}
  104.     	}
  105.     }
  106.     bool ok=true;
  107.     for (int i=0; i<root_nodes.size(); i++){
  108.     	if (!used[root_nodes[i]]) ok=false;
  109.     }
  110.     return ok;
  111. }
  112.  
  113. void solve(){
  114. 	int n; cin>>n;
  115. 	int m; cin>>m;
  116. 	vector<tuple<int,int,int> > edges;
  117. 	for (int i=0; i<m; i++){
  118. 		int u,v,w; cin>>u>>v>>w;
  119. 		edges.push_back(make_tuple(u,v,w));
  120. 	}
  121. 	int lo=MAX, hi=-1;
  122. 	while(lo-1!=hi){
  123. 		int mid = (lo+hi)/2;
  124. 		if (cando(mid,edges,n)) lo=mid;
  125. 		else hi=mid;
  126. 	}
  127. 	if (lo!=MAX) cout<<lo<<'\n';
  128. 	else cout<<-1<<'\n';
  129. }
  130.  
  131. int main() {
  132. 	ios::sync_with_stdio(0);
  133. 	cin.tie(0);
  134.  
  135. 	int t; cin>>t;
  136. 	while(t--) solve();
  137.  
  138. 	return 0;
  139. }
Success #stdin #stdout 0.01s 18168KB
comments (?)
stdin
copy 
4
2 1
1 2 3
5 4
1 2 10
2 3 10
3 1 10
4 5 10
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 500
4 3 20
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 5
4 3 20
stdout
copy 
0
-1
20
5
https://ideone.com/SpbqAJ
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!