import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
class KragersMinCut
{
static int n=8;//Number of Vertices
static int[] u=new int[n];
static int[]rank =new int[n];
static class Edge //Edge which hols the source and destination
{
int s,d;//Source,Destination
Edge(int s,int d)
{
this.s=s;
this.d=d;
}
}
private static void InitializeUnionFindData()
{
for(int i=0;i<n;i++)
{
u[i]=i;
rank[i]=1;
}
}
private static int FIND(int xx) //Finding Parent using Path-Compression Heuristics
{
if(u[xx]!=u[u[xx]])
{
u[xx]=FIND(u[xx]);
}
return u[xx];
}
private static boolean UNION(int x,int y) //Union by Order-by-Rank to create evenly balanced search trees
{
int px=FIND(x),py=FIND(y);
if(rank[px]>rank[py])
{
int temp=px;
px=py;
py=temp;
}
else if(rank[px]==rank[py])
rank[py]++;
u[px]=py;
return true;
}
{
ArrayList<Edge> EdgeList=new ArrayList<Edge>();
for(int i=0;i<n;i++)
{
ArrayList<Integer>al=new ArrayList<Integer>();
for(int j=0;j<x.length();j++) //This loop is for parsing the input format which contained random spaces
{
if(x.charAt(j)<48 || x.charAt(j)>57)
continue;
int p=j;
while(p!=x.length()&&(x.charAt(p)>=48 && x.charAt(p)<=57))
{
input+=(x.charAt(p));
p++;
}
j=p;
al.
add(Integer.
parseInt(input.
trim())-1); }
for(int j=1;j<al.size();j++)
{
EdgeList.add(new Edge(al.get(0),al.get(j)));//Source,Destination
}
}
//Edge list ready
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 {
int vcnt=n;//Essentially n
InitializeUnionFindData();
while(vcnt>2)
{
Edge x
=EdgeList.
get((int)(Math.
random()*(EdgeList.
size()-1)+1));//Obtaining random valued element at index from EdgeList int s=x.s,d=x.d;
int ps=FIND(s),pd=FIND(d);
if(ps!=pd)//Contracting. Essentially making their parents equal
{
UNION(s,d);
vcnt--;
}
}
int CurrMinCutValue=0;
for(Edge i:EdgeList)
{
int px=FIND(i.s),py=FIND(i.d);
if(px!=py)//Since they belong to different Vertices
{
CurrMinCutValue++;
}
}
MinCut
=Math.
min(MinCut,CurrMinCutValue
);//Finding Minimum cut of all random runs }
}
}
aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7CmltcG9ydCBqYXZhLmlvLkZpbGVJbnB1dFN0cmVhbTsKaW1wb3J0IGphdmEuaW8uSU9FeGNlcHRpb247CmltcG9ydCBqYXZhLmlvLklucHV0U3RyZWFtUmVhZGVyOwppbXBvcnQgamF2YS51dGlsLkFycmF5TGlzdDsKCmNsYXNzIEtyYWdlcnNNaW5DdXQKewogICAgc3RhdGljIGludCBuPTg7Ly9OdW1iZXIgb2YgVmVydGljZXMKICAgIHN0YXRpYyBpbnRbXSB1PW5ldyBpbnRbbl07CiAgICBzdGF0aWMgaW50W11yYW5rID1uZXcgaW50W25dOwoKICAgIHN0YXRpYyBjbGFzcyBFZGdlIC8vRWRnZSB3aGljaCBob2xzIHRoZSBzb3VyY2UgYW5kIGRlc3RpbmF0aW9uCiAgICB7CiAgICAgICAgaW50IHMsZDsvL1NvdXJjZSxEZXN0aW5hdGlvbgogICAgICAgIEVkZ2UoaW50IHMsaW50IGQpCiAgICAgICAgewogICAgICAgICAgICB0aGlzLnM9czsKICAgICAgICAgICAgdGhpcy5kPWQ7CiAgICAgICAgfQogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgSW5pdGlhbGl6ZVVuaW9uRmluZERhdGEoKQogICAgewogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICB1W2ldPWk7CiAgICAgICAgICAgIHJhbmtbaV09MTsKICAgICAgICB9CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgaW50IEZJTkQoaW50IHh4KSAvL0ZpbmRpbmcgUGFyZW50IHVzaW5nIFBhdGgtQ29tcHJlc3Npb24gSGV1cmlzdGljcwogICAgewogICAgICAgIGlmKHVbeHhdIT11W3VbeHhdXSkKICAgICAgICB7CiAgICAgICAgICAgIHVbeHhdPUZJTkQodVt4eF0pOwogICAgICAgIH0KICAgICAgICByZXR1cm4gdVt4eF07CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBVTklPTihpbnQgeCxpbnQgeSkgLy9VbmlvbiBieSBPcmRlci1ieS1SYW5rIHRvIGNyZWF0ZSBldmVubHkgYmFsYW5jZWQgc2VhcmNoIHRyZWVzCiAgICB7CiAgICBpbnQgcHg9RklORCh4KSxweT1GSU5EKHkpOwogICAgaWYocmFua1tweF0+cmFua1tweV0pCiAgICB7CiAgICAgICAgaW50IHRlbXA9cHg7CiAgICAgICAgcHg9cHk7CiAgICAgICAgcHk9dGVtcDsKICAgIH0KICAgIGVsc2UgaWYocmFua1tweF09PXJhbmtbcHldKQogICAgICAgIHJhbmtbcHldKys7CgogICAgdVtweF09cHk7CiAgICByZXR1cm4gdHJ1ZTsKICAgIH0KCgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIElPRXhjZXB0aW9uCgl7CiAgICAgICAgCgkJQnVmZmVyZWRSZWFkZXIgYnI9bmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKICAgICAgICBBcnJheUxpc3Q8RWRnZT4gRWRnZUxpc3Q9bmV3IEFycmF5TGlzdDxFZGdlPigpOwogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBTdHJpbmcgeD1ici5yZWFkTGluZSgpOwogICAgICAgICAgICBBcnJheUxpc3Q8SW50ZWdlcj5hbD1uZXcgQXJyYXlMaXN0PEludGVnZXI+KCk7CiAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8eC5sZW5ndGgoKTtqKyspIC8vVGhpcyBsb29wIGlzIGZvciBwYXJzaW5nIHRoZSBpbnB1dCBmb3JtYXQgd2hpY2ggY29udGFpbmVkIHJhbmRvbSBzcGFjZXMKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYoeC5jaGFyQXQoaik8NDggfHwgeC5jaGFyQXQoaik+NTcpCiAgICAgICAgICAgICAgICAgICAgY29udGludWU7CgogICAgICAgICAgICAgICAgaW50IHA9ajsKICAgICAgICAgICAgICAgIFN0cmluZyBpbnB1dD0iIjsKICAgICAgICAgICAgICAgIHdoaWxlKHAhPXgubGVuZ3RoKCkmJih4LmNoYXJBdChwKT49NDggJiYgeC5jaGFyQXQocCk8PTU3KSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpbnB1dCs9KHguY2hhckF0KHApKTsKICAgICAgICAgICAgICAgICAgICBwKys7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBqPXA7CiAgICAgICAgICAgICAgICBhbC5hZGQoSW50ZWdlci5wYXJzZUludChpbnB1dC50cmltKCkpLTEpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGZvcihpbnQgaj0xO2o8YWwuc2l6ZSgpO2orKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgRWRnZUxpc3QuYWRkKG5ldyBFZGdlKGFsLmdldCgwKSxhbC5nZXQoaikpKTsvL1NvdXJjZSxEZXN0aW5hdGlvbgogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIC8vRWRnZSBsaXN0IHJlYWR5CiAgICAgICAgaW50IE1pbkN1dD1JbnRlZ2VyLk1BWF9WQUxVRTsKICAgICAgICBmb3IoaW50IHE9MDtxPChuKm4pKk1hdGgubG9nKG4pO3ErKykvL1J1bm5pbmcgdGhldGEobl4yKmxuKG4pKSB0aW1lcyBmb3IgYSBnb29kIGVzdGltYXRlLiBSdW5zIGluIGFib3V0IDIwIHNlY3MKICAgICAgICB7CiAgICAgICAgICAgIGludCB2Y250PW47Ly9Fc3NlbnRpYWxseSBuCiAgICAgICAgICAgIEluaXRpYWxpemVVbmlvbkZpbmREYXRhKCk7CiAgICAgICAgICAgIHdoaWxlKHZjbnQ+MikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgRWRnZSB4PUVkZ2VMaXN0LmdldCgoaW50KShNYXRoLnJhbmRvbSgpKihFZGdlTGlzdC5zaXplKCktMSkrMSkpOy8vT2J0YWluaW5nIHJhbmRvbSB2YWx1ZWQgZWxlbWVudCBhdCBpbmRleCBmcm9tIEVkZ2VMaXN0CiAgICAgICAgICAgICAgICBpbnQgcz14LnMsZD14LmQ7CiAgICAgICAgICAgICAgICBpbnQgcHM9RklORChzKSxwZD1GSU5EKGQpOwogICAgICAgICAgICAgICAgaWYocHMhPXBkKS8vQ29udHJhY3RpbmcuIEVzc2VudGlhbGx5IG1ha2luZyB0aGVpciBwYXJlbnRzIGVxdWFsCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgVU5JT04ocyxkKTsKICAgICAgICAgICAgICAgICAgICB2Y250LS07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaW50IEN1cnJNaW5DdXRWYWx1ZT0wOwogICAgICAgICAgICBmb3IoRWRnZSBpOkVkZ2VMaXN0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgcHg9RklORChpLnMpLHB5PUZJTkQoaS5kKTsKICAgICAgICAgICAgICAgIGlmKHB4IT1weSkvL1NpbmNlIHRoZXkgYmVsb25nIHRvIGRpZmZlcmVudCBWZXJ0aWNlcwogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIEN1cnJNaW5DdXRWYWx1ZSsrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIE1pbkN1dD1NYXRoLm1pbihNaW5DdXQsQ3Vyck1pbkN1dFZhbHVlKTsvL0ZpbmRpbmcgTWluaW11bSBjdXQgb2YgYWxsIHJhbmRvbSBydW5zCiAgICAgICAgfQogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihNaW5DdXQpOwoJfQp9