Advertisement
Guest User

Untitled

a guest
Aug 20th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define Maxx 1000001
  3. using namespace std;
  4. struct node{
  5. int x, y ;
  6. } ;
  7.  
  8. bool compare(node a, node b){
  9. if(a.x < a.y){
  10. return true ;
  11. }
  12. else if(a.x == b.x){
  13. if(a.y < b.y) {
  14. return true ;
  15. }
  16. else{
  17. return false ;
  18. }
  19. }
  20. else{
  21. return false ;
  22. }
  23. }
  24. node sample[Maxx] ;
  25. vector <int> g[Maxx] ;
  26. bool visited[Maxx] ;
  27. int low[Maxx] , discover[Maxx] , timer = 1 , j = 0 ;
  28. void dfs(int start , int parent){
  29. visited[start] = true ;
  30. low[start] = discover[start] = ++timer ;
  31. for(int a : g[start]){
  32. if(a == parent) continue ;
  33. if(visited[a]){
  34. low[start] = min(low[start] , discover[a]) ;
  35. }
  36. else{
  37. dfs(a , start) ;
  38. low[start] = min(low[start] , low[a]) ;
  39. if(low[a] > discover[start]){
  40. sample[j].x = min(a,start) ;
  41. sample[j++].y = max(a,start) ;
  42. }
  43. }
  44. }
  45. }
  46.  
  47. int main() {
  48. int n , m ;
  49. cin >> n >> m ;
  50. while(m--){
  51. int u , v ;
  52. cin >> u >> v ;
  53. g[u].push_back(v) ;
  54. g[v].push_back(u) ;
  55. }
  56. for(int i = 0 ; i < n ; i++){
  57. visited[i] = false ;
  58. low[i] = -1 ;
  59. discover[i] = -1 ;
  60. }
  61. for(int i = 0 ; i < n ; i++){
  62. if(!visited[i])
  63. dfs(i , -1) ;
  64. }
  65. sort(sample , sample + j , compare) ;
  66. int i = 0 ;
  67. while(j--){
  68. cout << sample[i].x << " " <<sample[i++].y << "\n" ;
  69. }
  70. timer = 1 ;
  71. return 0 ;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement