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);
    
  }

}