fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n, m;
  4. vector<int> adj[2501]; 
  5. // 0(n(n + m)) 
  6. int cycle(int start){
  7. 	vector<int> dis(n + 1, -1);
  8. 	queue<int> bfs;
  9. 	int ans = INT_MAX;  
  10. 	bfs.push(start);
  11. 	dis[start] = 0; 
  12. 	while(not bfs.empty()){
  13. 		int node = bfs.front();
  14. 		bfs.pop();
  15. 		for(int adj_node : adj[node]){
  16. 			if(dis[adj_node] == -1){
  17. 				dis[adj_node] = dis[node] + 1;
  18. 				bfs.push(adj_node);  
  19. 			} 
  20. 			else if(dis[adj_node] >= dis[node]){
  21. 				ans = min(ans, dis[adj_node] + dis[node] + 1);  
  22. 			} 
  23. 		} 
  24. 	} 
  25. 	return ans;  
  26. }
  27. int main(){
  28. 	cin >> n >> m;
  29. 	for(int i = 1;i <= m;i++){
  30. 		int a, b;
  31. 		cin >> a >> b;
  32. 		adj[a].push_back(b);
  33. 		adj[b].push_back(a); 
  34. 	} 
  35. 	int ans = INT_MAX;  
  36. 	for(int i = 1;i <= n;i++){
  37. 		ans = min(ans, cycle(i));  
  38. 	} 
  39. 	if(ans == INT_MAX) cout << -1 << endl;
  40. 	else cout << ans << endl;  
  41. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/EBoo6H
language:
C++14 (gcc 8.3)
created:
1 day 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!