package graph;

// graphes par listes d'adjacence

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class AdjList<V> {

  private Map<V, LinkedList<V>> adj;
  
  AdjList() {
    this.adj = new HashMap<V, LinkedList<V>>();
  }
  
  void addVertex(V u) {
    List<V> s = this.adj.get(u);
    if (s == null) this.adj.put(u, new LinkedList<V>());
  }
  
  boolean hasEdge(V x, V y) {
    List<V> s = this.adj.get(x);
    return s != null && s.contains(y);
  }
  
  void addEdge(V x, V y) {
    addVertex(x);
    this.adj.get(x).add(y);
  }
  
  void removeEdge(V x, V y) {
    List<V> s = this.adj.get(x);
    if (s != null) s.remove(y);
  }
  
  List<V> successors(V u) {
    return this.adj.get(u);
  }
  
  Set<V> vertices() {
    return this.adj.keySet();
  }
    
}

class DFSAdjList<V> {
  
  private AdjList<V> g;
  private HashMap<V, Integer> visited;
  private int count;
  
  DFSAdjList(AdjList<V> g) {
    this.g = g;
    this.visited = new HashMap<V, Integer>();
    this.count = 0;
  }
  
  void dfs(V v) {
    if (this.visited.containsKey(v)) return;
    this.visited.put(v, count++);
    for (V w : g.successors(v))
      dfs(w);
  }
  
  void dfs() {
    for (V v : g.vertices())
      dfs(v);
  }

  int dfsNum(V v) {
    dfs(v);
    return this.visited.get(v);
  }
  
}

class BFSAdjList<V> {
  
  private AdjList<V> g;
  private HashMap<V, Integer> visited;
  private int count;
  
  BFSAdjList(AdjList<V> g) {
    this.g = g;
    this.visited = new HashMap<V, Integer>();
    this.count = 0;
  }

  void bfs(V v) {
    Queue<V> q = new LinkedList<V>();
    if (!this.visited.containsKey(v)) q.add(v);
    while (!q.isEmpty()) {
      v = q.poll();
      this.visited.put(v, count++);
      for (V w : g.successors(v))
        if (!this.visited.containsKey(w)) q.add(w);
    }
  }
  
  void bfs() {
    for (V v : g.vertices())
      bfs(v);
  }

  int bfsNum(V v) {
    bfs(v);
    return this.visited.get(v);
  }
 
}

class TestAdjList {
  public static void main(String[] args) {
    AdjList<Integer> g = new AdjList<Integer>();
    g.addVertex(1);
    g.addVertex(3);
    g.addVertex(5);
    g.addEdge(1, 3);
    g.addEdge(3, 5);
    assert (g.hasEdge(1, 3));
    g.removeEdge(1, 3);
    assert (!g.hasEdge(1, 3));
    assert (!g.hasEdge(3, 1));
    assert (g.hasEdge(3, 5));
    
    g.addEdge(1, 3);
    g.addEdge(5, 3);
    
    // DFS
    DFSAdjList<Integer> dfs = new DFSAdjList<Integer>(g);
    dfs.dfs(3);
    for (int v : g.vertices())
      System.out.println("dfs(" + v + ")=" + dfs.dfsNum(v));
    System.out.println();
    
    // BFS
    BFSAdjList<Integer> bfs = new BFSAdjList<Integer>(g);
    bfs.bfs();
    for (int v : g.vertices())
      System.out.println("bfs(" + v + ")=" + bfs.bfsNum(v));
    
    System.out.println("TestAdjList OK");
     }
}