fork(2) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Main{
  6.  
  7. 	static int n, e; //vertices, arcos
  8. 	static int MAX=1010;     
  9. 	static ArrayList<Integer> ady[]=new ArrayList [MAX];
  10. 	static boolean marked[]=new boolean [MAX];
  11. 	static int prev[]=new int [MAX];
  12. 	static int dfs_low[]=new int [MAX];
  13. 	static int dfs_num[]=new int [MAX];
  14. 	static int itsmos[]=new int [MAX];
  15. 	static ArrayList<Edge> bridges;
  16. 	static int dfsRoot, rootChildren, cont;
  17.  
  18. 	public static void main (String[] args) throws java.lang.Exception{
  19. 		int i;
  20. 		n = 6;
  21. 		init();
  22.  
  23. 		ady[0].add(1); ady[1].add(0);
  24. 		ady[1].add(2); ady[2].add(1);
  25. 		ady[4].add(1); ady[1].add(4);
  26. 		ady[3].add(4); ady[4].add(3);
  27. 		ady[4].add(5); ady[5].add(4);
  28.  
  29.  
  30. 		puntosArticulacionYPuentes();
  31.  
  32. 		/*****************************/
  33. 		n = 6;
  34. 		init();
  35.  
  36. 		ady[0].add(1); ady[1].add(0);
  37. 		ady[1].add(2); ady[2].add(1);
  38. 		ady[4].add(1); ady[1].add(4);
  39. 		ady[3].add(1); ady[1].add(3);
  40. 		ady[4].add(5); ady[5].add(4);
  41. 		ady[1].add(5); ady[5].add(1);
  42.  
  43. 		puntosArticulacionYPuentes();
  44.  
  45. 		/*****************************/
  46. 		n = 3;
  47. 		init();
  48.  
  49. 		ady[0].add(1); ady[1].add(0);
  50. 		ady[1].add(2); ady[2].add(1);
  51. 		ady[2].add(0); ady[0].add(2);
  52.  
  53. 		puntosArticulacionYPuentes();
  54. 	}
  55.  
  56. 	static void puntosArticulacionYPuentes(){
  57. 		int i;
  58. 		cont = 0;
  59. 		dfsRoot = 0;
  60. 		rootChildren = 0;
  61. 		dfs(0);
  62.  
  63. 		System.out.println("PUNTOS DE ARTICULACIÓN");
  64. 		for(i = 0; i < n; i++ ){
  65. 			if( itsmos[i] == 1 ){
  66. 				if( i == dfsRoot ){
  67. 					if( rootChildren > 1 ) System.out.println(i);
  68. 				}else System.out.println(i);	
  69. 			} 
  70. 		}
  71.  
  72. 		System.out.println("PUENTES");
  73. 		for(i = 0; i < bridges.size(); i++ ){
  74. 			System.out.println(bridges.get(i).src + " " + bridges.get(i).dest );
  75. 		}
  76. 	}
  77.  
  78. 	static void init() {
  79. 	    bridges=new ArrayList<Edge>();
  80. 	    cont=0;
  81. 	    int i;
  82. 	    for(i=0; i<n; i++){
  83. 	        ady[i]=new ArrayList<Integer>();
  84. 	        marked[i]=false;
  85. 	        prev[i]=-1;
  86. 	        itsmos[i]=0;
  87. 	    }
  88. 	}
  89.  
  90. 	static void dfs(int u){
  91. 	    dfs_low[u]=cont;
  92. 	    dfs_num[u]=cont;
  93. 	    cont++;
  94. 	    marked[u]=true;
  95. 	    int j, v;
  96.  
  97. 	    for(j=0; j<ady[u].size(); j++){
  98. 	        v=ady[u].get(j);
  99. 	        if(!marked[v]){
  100. 	            prev[v]=u;
  101. 	            //Caso especial 
  102. 	            if(u==dfsRoot){
  103. 	                rootChildren++;
  104. 	            }
  105. 	            dfs(v);
  106. 	            //PARA ITSMOS
  107. 	            if(dfs_low[v]>=dfs_num[u]){
  108. 	                itsmos[u]=1;
  109. 	            }
  110. 	            //PARA PUENTES
  111. 	            if(dfs_low[v]>dfs_num[u]){
  112. 	                bridges.add(new Edge(Math.min(u,v),Math.max(u,v)));
  113. 	            }
  114. 	            dfs_low[u]=Math.min(dfs_low[u], dfs_low[v]);
  115. 	        }else if(v!=prev[u]){ //Arco que no sea backtrack
  116. 	            dfs_low[u]=Math.min(dfs_low[u], dfs_num[v]);
  117. 	        }
  118. 	    }
  119. 	}
  120.  
  121. 	static class Edge{
  122.  
  123. 	    public int src, dest;
  124.  
  125. 	    public Edge(int s, int d) {
  126. 	        this.src = s;
  127. 	        this.dest = d;
  128. 	    }
  129. 	}
  130. }
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
PUNTOS DE ARTICULACIÓN
1
4
PUENTES
1 2
3 4
4 5
1 4
0 1
PUNTOS DE ARTICULACIÓN
1
PUENTES
1 2
1 3
0 1
PUNTOS DE ARTICULACIÓN
PUENTES
https://ideone.com/Z6Z6CI
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

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!