class OGraph { // Graphes orientés private List [] succ ; OGraph (int size) { succ = new List[size] ;} void arc(int src, int dst) { succ[src] = new List (dst,succ[src]) ; } OGraph inverse () { OGraph r = new OGraph(succ.length) ; for (int src = 0 ; src < succ.length ; src++) for (List p = succ[src] ; p != null ; p = p.next) r.arc(p.val,src) ; return r ; } void descendre(int s, int orderSC, int [] numSC) { numSC[s] = -orderSC ; for (List p = succ[s] ; p != null ; p = p.next) if (numSC[p.val] <= 0 && numSC[p.val] != -orderSC) descendre(p.val, orderSC, numSC) ; } void remonter(int s, int orderSC, int [] numSC) { numSC[s] = orderSC ; System.out.print(" " + s) ; for (List p = succ[s] ; p != null ; p = p.next) if (numSC[p.val] == -orderSC) remonter(p.val, orderSC, numSC) ; } void findStrongConnect () { OGraph ig = inverse () ; int orderSC = 0 ; int [] numSC = new int[succ.length] ; for (int s = 0 ; s < succ.length ; s++) { if (numSC[s] <= 0) { ++orderSC ; System.out.print("SCC " + orderSC + ":") ; descendre(s, orderSC, numSC) ; ig.remonter(s, orderSC, numSC) ; System.out.println() ; } } } public static void main (String [] argv) { OGraph g = new OGraph(11) ; g.arc(0,1) ; g.arc(0,4) ; g.arc(1,2) ; g.arc(1,3) ; g.arc(1,8) ; g.arc(2,3) ; g.arc(4,5) ; g.arc(4,0) ; g.arc(4,5) ; g.arc(5,6) ; g.arc(5,7) ; g.arc(5,8) ; g.arc(9,10) ; g.arc(0,10) ; g.arc(10,4) ; g.print() ; g.findStrongConnect() ; } } |