Проверить , является ли граф связным

;; Дать следующую вершину при обходе в глубину
 
(defun get-next (graph v chk)
  (iter (for e in graph) 
   (when (and (eq v (car e)) (not (member (cadr e) chk))) (return (cadr e)))
   (when (and (eq v (cadr e)) (not (member (car e) chk))) (return (car e)))))
 
;; Обход в глубину с построением каркаса
 
(defun dfs (graph s chk tree)
  (let ((next-v (get-next graph (car chk) chk)))
    (cond ((null s) tree)
          ((null next-v) (dfs graph (cdr s) chk tree))
          (t (dfs graph (cons next-v s) (cons next-v chk) (cons (list next-v (car chk)) tree))))))
 
;; Решение задачи
 
(defun task (graph)
  (let ((vlist (setof (apply 'append graph)))
        (tree  (dfs graph (list (caar graph)) (list (caar graph)) nil)))
    (= (length (setof (apply 'append tree))) (length vlist))))
 
(task '((a b) (b c) (c d)))
==> T
 
(task '((a b) (b c) (e d)))
==> NIL