import java.awt.*;
import Point;
import Queue;
class Graph
  {
    int V, E;
    Node[] adj;
    Point[] p;
    boolean[] visited;

    boolean[] onPQ;
    int[] dad;

    int delay;
    Graphics page;

    Graph(int V, double d)
      {
        this.V = V; this.E = 0;
        adj = new Node[V]; 
        p = new Point[V]; 
        for (int i = 0; i < V; i++)
          p[i] = new Point(Math.random(), Math.random());
        for (int i = 0; i < V; i++)
          adj[i] = new Node(i, null);
        for (int i = 0; i < V; i++)
          for (int j = i+1; j < V; j++)
            if (Point.distance(p[i], p[j]) < d)
              { E++;
                adj[j].next = new Node(i, adj[j].next);
                adj[i].next = new Node(j, adj[i].next);
              }
        System.out.println(V + " vertices, " + E + " edges.");
      }
    void drawVertex(Point p, Color c)
      { 
        int h = page.getClipRect().height;
        int w = page.getClipRect().width;
        page.setColor(c);
        for (int j = 0; j < delay; j++)
          page.fillOval( (int) (h*p.x)-3, (int) (w*p.y)-3, 6, 6);
      }
    void drawEdge(Point p, Point q, Color c)
      { 
        int h = page.getClipRect().height;
        int w = page.getClipRect().width;
        page.setColor(c);
        for (int j = 0; j < delay; j++)
          page.drawLine( (int) (h*p.x), (int) (w*p.y), 
                         (int) (h*q.x), (int) (w*q.y));
      }
    void paint(Graphics page)
      {
        this.page = page; this.delay = 1;
        for (int i = 0; i < this.V; i++)
          drawVertex(p[i], Color.white);
        for (int i = 0; i < this.V; i++)
          for (Node s = adj[i].next; s != null; s = s.next)
            drawEdge(p[i], p[s.v], Color.white);
      }
    void dfsR(int k)
      { 
        visited[k] = true; drawVertex(this.p[k], Color.black);
        for (Node s = adj[k].next; s != null; s = s.next)
          if (!visited[s.v]) 
            { 
              drawEdge(p[k], p[s.v], Color.red);
              dfsR(s.v); 
            }
        drawVertex(p[k], Color.red);
      }
    void dfs(int delay)
      { 
        this.delay = delay;
        visited = new boolean[V];
        for (int i = 0; i < V; i++) visited[i] = false;
        dfsR(0);
      }
    void bfs(int delay)
      { int k;
        this.delay = delay;
        visited = new boolean[V];
        for (int i = 0; i < V; i++) visited[i] = false;
        Queue fringe = new Queue(V);
        fringe.put(0); drawVertex(p[0], Color.black);
        while (!fringe.empty())
          if (!visited[k = fringe.get()])
            {
              visited[k] = true; drawVertex(p[k], Color.red);
              for (Node s = adj[k].next; s != null; s = s.next)
                if (!visited[s.v]) 
                  { 
                    drawEdge(p[k], p[s.v], Color.red);
                    fringe.put(s.v); drawVertex(p[s.v], Color.black);
                  }
            }
      }
  }