;;; Connected Components
;;; uses adjacency-list form
;;; uses dfs

(load "p87.lisp")

(defun components (graph)
  (comp-aux graph nil nil (nodes graph))
  )

(defun comp-aux (graph comps ja-foi a-tentar)
  "Finds the remaining connected components of a GRAPH, given
   the already known components in a list COMPS, a list of
   nodes already reached in JA-FOI, and nodes to still try in
   A-TENTAR"
  (cond
   ((null a-tentar) comps)
   ((member (car a-tentar) ja-foi)
    (comp-aux graph comps ja-foi (cdr a-tentar)))
   (t (let ((comp (dfs graph (car a-tentar))))
	(comp-aux graph (cons comp comps) (append comp ja-foi) (cdr a-tentar))
	))
   )
  )

(defun nodes (graph)
  (mapcar #'car graph)
  )