Advertisement
Guest User

Untitled

a guest
Aug 3rd, 2015
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.39 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.util.ArrayList;
  6.  
  7. class KragersMinCut
  8. {
  9. static int n=200;//Number of Vertices
  10. static int[] u=new int[n];
  11. static int[]rank =new int[n];
  12.  
  13. static class Edge //Edge which hols the source and destination
  14. {
  15. int s,d;//Source,Destination
  16. Edge(int s,int d)
  17. {
  18. this.s=s;
  19. this.d=d;
  20. }
  21. }
  22.  
  23. private static void InitializeUnionFindData()
  24. {
  25. for(int i=0;i<n;i++)
  26. {
  27. u[i]=i;
  28. rank[i]=1;
  29. }
  30. }
  31.  
  32. private static int FIND(int xx) //Finding Parent using Path-Compression Heuristics
  33. {
  34. if(u[xx]!=u[u[xx]])
  35. {
  36. u[xx]=FIND(u[xx]);
  37. }
  38. return u[xx];
  39. }
  40.  
  41. private static boolean UNION(int x,int y) //Union by Order-by-Rank to create evenly balanced search trees
  42. {
  43. int px=FIND(x),py=FIND(y);
  44. if(rank[px]>rank[py])
  45. {
  46. int temp=px;
  47. px=py;
  48. py=temp;
  49. }
  50. else if(rank[px]==rank[py])
  51. rank[py]++;
  52.  
  53. u[px]=py;
  54. return true;
  55. }
  56.  
  57.  
  58. public static void main(String[] args) throws IOException
  59. {
  60. BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  61. ArrayList<Edge> EdgeList=new ArrayList<Edge>();
  62. for(int i=0;i<n;i++)
  63. {
  64. String x=br.readLine();
  65. ArrayList<Integer>al=new ArrayList<Integer>();
  66. for(int j=0;j<x.length();j++) //This loop is for parsing the input format
  67. {
  68. if(x.charAt(j)<48 || x.charAt(j)>57)
  69. continue;
  70.  
  71. int p=j;
  72. String input="";
  73. while(p!=x.length()&&(x.charAt(p)>=48 && x.charAt(p)<=57))
  74. {
  75. input+=(x.charAt(p));
  76. p++;
  77. }
  78. j=p;
  79. al.add(Integer.parseInt(input.trim())-1);
  80. }
  81. for(int j=1;j<al.size();j++)
  82. {
  83. EdgeList.add(new Edge(al.get(0),al.get(j)));//Source,Destination
  84. }
  85. }
  86. //Edge list ready
  87. int MinCut=Integer.MAX_VALUE;
  88. for(int q=0;q<(n*n)*Math.log(n);q++)//Running theta(n^2*ln(n)) times for a good estimate. Runs in about 20 secs
  89. {
  90. int vcnt=n;//Essentially n
  91. InitializeUnionFindData();
  92. while(vcnt>2)
  93. {
  94. Edge x=EdgeList.get((int)(Math.random()*(EdgeList.size()-1)+1));//Obtaining random valued element at index from EdgeList
  95. int s=x.s,d=x.d;
  96. int ps=FIND(s),pd=FIND(d);
  97. if(ps!=pd)//Contracting. Essentially making their parents equal
  98. {
  99. UNION(s,d);
  100. vcnt--;
  101. }
  102. }
  103. int CurrMinCutValue=0;
  104. for(Edge i:EdgeList)
  105. {
  106. int px=FIND(i.s),py=FIND(i.d);
  107. if(px!=py)//Since they belong to different Vertices
  108. {
  109. CurrMinCutValue++;
  110. }
  111. }
  112. MinCut=Math.min(MinCut,CurrMinCutValue);//Finding Minimum cut of all random runs
  113. }
  114. System.out.println(MinCut);
  115. }
  116. }
  117.  
  118. Edge x=EdgeList.get((int)(Math.random()*(EdgeList.size()-1)+1));
  119.  
  120. Edge x=EdgeList.get((int)(Math.random()*(EdgeList.size())));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement