Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define Maxx 1000001
- using namespace std;
- struct node{
- int x, y ;
- } ;
- bool compare(node a, node b){
- if(a.x < a.y){
- return true ;
- }
- else if(a.x == b.x){
- if(a.y < b.y) {
- return true ;
- }
- else{
- return false ;
- }
- }
- else{
- return false ;
- }
- }
- node sample[Maxx] ;
- vector <int> g[Maxx] ;
- bool visited[Maxx] ;
- int low[Maxx] , discover[Maxx] , timer = 1 , j = 0 ;
- void dfs(int start , int parent){
- visited[start] = true ;
- low[start] = discover[start] = ++timer ;
- for(int a : g[start]){
- if(a == parent) continue ;
- if(visited[a]){
- low[start] = min(low[start] , discover[a]) ;
- }
- else{
- dfs(a , start) ;
- low[start] = min(low[start] , low[a]) ;
- if(low[a] > discover[start]){
- sample[j].x = min(a,start) ;
- sample[j++].y = max(a,start) ;
- }
- }
- }
- }
- int main() {
- int n , m ;
- cin >> n >> m ;
- while(m--){
- int u , v ;
- cin >> u >> v ;
- g[u].push_back(v) ;
- g[v].push_back(u) ;
- }
- for(int i = 0 ; i < n ; i++){
- visited[i] = false ;
- low[i] = -1 ;
- discover[i] = -1 ;
- }
- for(int i = 0 ; i < n ; i++){
- if(!visited[i])
- dfs(i , -1) ;
- }
- sort(sample , sample + j , compare) ;
- int i = 0 ;
- while(j--){
- cout << sample[i].x << " " <<sample[i++].y << "\n" ;
- }
- timer = 1 ;
- return 0 ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement