package com.data.struct; import java.util.Arrays; import java.util.Comparator; import java.util.Random; public class StrongConnectedComponent { private Node[] list; private int time=0; private boolean isComponet=false; public StrongConnectedComponent(){ } public StrongConnectedComponent(int v,int e){ list=new Node[v]; for(int i=0;i<v;i++){ Node node=new Node(); node.id=i; list[i]=node; } for(int i=0;i<e;i++){ int v1=new Random().nextInt(v); int v2=new Random().nextInt(v); if(v1==v2){ continue; } while(true){ Node node=list[v1]; boolean already=false; while(node.next!=null){ if(node.next.id==v2){ already=true; break; } node=node.next; } if(already==true){ break; } Node ex=new Node(); ex.id=v2; node.next=ex; break; } } } public void strongComponentDepthFirstSearch(Node[]list){ Arrays.sort(list, new Comparator<Node>() { @Override public int compare(Node o1, Node o2) { if(o1.f>o2.f){ return -1; }else if(o1.f<o2.f){ return 1; }else{ return 0; } } }); int[]order=new int[list.length]; for(int i=0;i<list.length;i++){ order[i]=list[i].id; } Arrays.sort(list, new Comparator<Node>() { @Override public int compare(Node o1, Node o2) { if(o1.id<o2.id){ return -1; }else if(o1.id>o2.id){ return 1; }else{ return 0; } } }); for(int i=0;i<order.length;i++){ if(list[order[i]].color==Node.WHITE){ dfsVisit(list[order[i]]); } } } public void depthFirstSearch(){ for(int i=0;i<list.length;i++){ if(list[i].color==Node.WHITE){ dfsVisit(list[i]); } } } private void dfsVisit(Node node){ time++; node.d=time; node.color=Node.GRAY; Node w=list[node.id]; Node u=w; while(w.next!=null){ if(list[w.next.id].color==Node.WHITE){ list[w.next.id].color=Node.GRAY; list[w.next.id].parent=u; dfsVisit(list[w.next.id]); } w=w.next; } node.color=Node.BLACK; time++; node.f=time; } public void printStrongComponent(StrongConnectedComponent t){ System.out.println("strong component"); for(int i=0;i<t.list.length;i++){ Node s=t.list[i]; isComponet=false; printStrongComponent(s); System.out.println(); } } public void printStrongComponent(Node v){ if(v.parent==null&&!isComponet){ return; }else if(v.parent==null&&isComponet){ System.out.print(v.id+"=>"); }else { isComponet=true; printStrongComponent(v.parent); System.out.print(v.id+"=>"); } } public void printDepth(Node v){ Node s=list[0]; if(v==s){ System.out.print(s.id+"=>"); }else if(v.parent==null){ System.out.print(v.id+"=>"); }else { printDepth(v.parent); System.out.print(v.id+"=>"); } } public void print(){ for(int i=0;i<list.length;i++){ Node node=list[i]; System.out.print(node.id+"=>"); while(node.next!=null){ System.out.print(node.next.id+"=>"); node=node.next; } System.out.println(); } } public void printAllDepth(){ System.out.println("path"); for(int i=0;i<list.length;i++){ printDepth(list[i]); System.out.println(); } } public StrongConnectedComponent tansform(){ StrongConnectedComponent grapic=new StrongConnectedComponent(); grapic.list=new Node[list.length]; for(int i=0;i<list.length;i++){ Node node=new Node(); node.id=list[i].id; node.d=list[i].d; node.f=list[i].f; grapic.list[i]=node; } for(int i=0;i<list.length;i++){ Node node=list[i]; Node w=node; while(w.next!=null){ Node last=grapic.list[w.next.id]; while(last.next!=null){ last=last.next; } Node next=new Node(); next.id=node.id; last.next=next; w=w.next; } } return grapic; } public static class Node{ public static final int WHITE=1; public static final int BLACK=2; public static final int GRAY=3; private int id; private Node next; private int color=WHITE; private int d=Integer.MAX_VALUE; private Node parent; private int f; } public static void main(String[] args)throws Exception { StrongConnectedComponent g=new StrongConnectedComponent(5,10); g.print(); g.depthFirstSearch(); g.printAllDepth(); StrongConnectedComponent t=g.tansform(); System.out.println("t======"); t.print(); t.strongComponentDepthFirstSearch(t.list); t.printStrongComponent(t); } }