fork(6) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Main{
  6.  
  7. 	static int n = 5000; // Máxima cantidad de nodos
  8. 	static int dfs_low[] = new int[n];
  9. 	static int dfs_num[] = new int[n];
  10. 	static boolean visited[] = new boolean[n];
  11. 	static Stack<Integer> s;
  12. 	static int dfsCont, cantSCC;
  13. 	static ArrayList<Integer> ady[] = new ArrayList[n];
  14.  
  15. 	public static void main (String[] args) throws java.lang.Exception{
  16. 		Scanner sc = new Scanner( System.in );
  17.  
  18. 		int v, e, i, a, b;
  19.  
  20. 		v = sc.nextInt();
  21. 		e = sc.nextInt();
  22.  
  23. 		//LIMPIAR ADYACENCIAS
  24. 		for( i = 0; i < v; i++ ){
  25. 			ady[i] = new ArrayList<Integer>();
  26. 		}
  27.  
  28. 		while( e > 0 ){
  29. 			e--;
  30. 			a = sc.nextInt();
  31. 			b = sc.nextInt();
  32.  
  33. 			ady[a].add(b);
  34. 		}
  35.  
  36. 		for( i = 0; i < v; i++ ){
  37. 			visited[i] = false;
  38. 			dfs_num[i] = -1;
  39. 		}
  40. 		s = new Stack<Integer>();
  41. 		dfsCont = 0;
  42. 		cantSCC = 0;
  43. 		tarjanSCC(0);
  44. 	}
  45.  
  46. 	public static void tarjanSCC( int u ){
  47. 		dfs_low[u] = dfs_num[u] = dfsCont;
  48. 		dfsCont++;
  49. 		s.push(u);
  50. 		visited[u] = true;
  51.  
  52. 		int j, v;
  53.  
  54. 		for( j = 0; j < ady[u].size(); j++ ){
  55. 			v = ady[u].get( j );
  56.  
  57. 			if( dfs_num[v] == -1 ){
  58. 				tarjanSCC( v );
  59. 			}
  60.  
  61. 			if( visited[v] ){
  62. 				dfs_low[u] = Math.min( dfs_low[u], dfs_low[v] );
  63. 			}
  64. 		}
  65.  
  66. 		if( dfs_low[u] == dfs_num[u] ){
  67. 			cantSCC++;
  68. 			System.out.println("COMPONENTE CONEXA #" + cantSCC );
  69. 			while( !s.empty() ){
  70. 				v = s.peek();
  71. 				s.pop();
  72. 				visited[v] = false;
  73. 				System.out.println(v);
  74. 				if( u == v ) break;
  75. 			}
  76. 		}
  77.  
  78. 	}
  79. }
  80.  
  81.  
Success #stdin #stdout 0.07s 4386816KB
comments (?)
stdin
copy 
8 9
0 1
1 3
3 4
4 5
5 7
7 6
6 4
3 2
2 1
stdout
copy 
COMPONENTE CONEXA #1
6
7
5
4
COMPONENTE CONEXA #2
2
3
1
COMPONENTE CONEXA #3
0
https://ideone.com/0OdhTe
language:
Java (HotSpot 12)
created:
7 years 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!