gistfile1.clj

(defn tarjan-stepper
  [graph]
  (fn this
    ([[components seen :as state] node]
     (if (contains? seen node)
       state
       (let [[components seen] (this components seen node)]
         [(conj components (get seen node)) seen]))) 
    ([components seen node]
     (reduce (fn [[components seen] subnode]
               (if (contains? seen subnode)
                 [components (update-in seen [node] conj subnode)]
                 (let [[components seen] (this components seen subnode)
                       subcomponent      (get seen subnode)]
                   (if (contains? subcomponent node)
                     [components (update-in seen [node] into subcomponent)]
                     [(conj components subcomponent) seen]))))
             [components (assoc seen node #{node})] (graph node)))))

(defn tarjan
  [graph]
  (first (reduce (tarjan-stepper graph) [#{} {}] (keys graph))))

(defn rand-graph [n density]
  (let [g (zipmap (range n) (repeat #{}))
        m (Math/ceil (* n (dec n) density))]
    (reduce (fn [g [x y]]
              (update-in g [x] conj y))
      g (take m (distinct (repeatedly (juxt #(rand-int n) #(rand-int n))))))))

{0
 #{33 65 2 34 99 70 7 10 43 77 46 48 49 82 83 23 55 24 88 57 26 58 28
   61 31 63},
 32
 #{0 34 4 37 69 39 40 9 73 42 74 11 43 75 77 14 47 17 52 84 21 53 89 90
   31},
 64
 #{64 96 1 66 5 70 40 41 73 10 42 11 43 75 77 50 51 86 23 55 25 89 59
   91 92 61 93 62 63},
 96 #{96 5 38 70 39 9 41 10 11 75 14 47 79 16 48 82 83 20 52 90 60 63},
 1
 #{64 65 98 5 72 9 43 46 47 48 17 18 54 24 88 57 89 58 27 61 30 62 95},
 33 #{32 1 2 67 36 38 39 13 14 47 21 53 22 88 58 90 28 60 92 29 31},
 65
 #{0 34 66 68 70 71 8 72 10 43 75 12 44 17 18 51 83 84 54 23 55 87 24
   90 60 93 95},
 97
 #{32 33 97 4 38 39 43 75 76 46 15 47 19 51 83 20 21 23 24 88 25 90 29
   63},
 2
 #{64 65 2 66 99 69 6 8 40 43 44 45 79 48 18 82 83 53 85 88 25 26 29 93
   30 31},
 34
 #{64 66 3 35 38 40 74 13 15 19 52 21 54 86 25 89 27 91 28 61 62 94 31
   63 95},
 66 #{98 36 70 40 9 73 10 74 11 43 77 14 79 82 20 86 55 88 60 29 30},
 98
 #{0 32 64 1 99 36 5 37 6 9 42 43 75 45 14 46 15 16 80 81 50 19 20 52
   87 56 88 57 89 61},
 3
 #{0 97 98 3 68 6 38 73 
10 43 75 76 14 46 80 17 49 81 50 82 20 84 86 92
   93 31 63},
 35
 #{0 64 33 2 98 67 36 6 70 7 71 10 11 43 77 48 80 51 84 53 86 24 57 89
   91 92},
 67
 #{64 33 2 34 35 7 39 71 8 40 9 10 42 76 45 48 81 50 82 51 21 53 23 55
   87 24 25 59 62},
 99
 #{96 65 97 67 36 69 38 10 42 12 13 15 47 81 85 22 87 56 89 59 91 60 93
   31 95},
 4
 #{0 64 97 37 69 7 8 9 10 74 43 75 12 77 79 16 17 51 83 21 86 25 28 92
   29 61 93 30 31},
 36
 #{32 1 3 99 4 68 5 72 43 75 15 48 49 81 50 20 54 86 55 56 57 90 59
   29},
 68 #{0 96 98 67 99 36 5 6 39 8 75 45 14 15 47 48 52 56 88 91 28 31},
 5
 #{96 97 99 68 5 38 41 10 43 12 79 16 80 19 51 53 55 87 56 25 57 91 28
   92 63},
 37
 #{0 64 65 2 34 35 36 68 37 69 6 71 10 74 75 14 16 48 50 19 51 52 54 86
   55 24 60 31 95},
 69 #{34 98 67 6 38 10 75 44 13 16 82 85 24 56 61},
 6
 #{64 66 67 4 36 68 69 38 71 41 73 10 11 45 78 15 47 48 80 81 53 85 22
   86 23 58 30 62},
 38
 #{0 96 1 33 2 66 35 37 69 8 14 46 78 16 83 84 21 55 87 26 27 92 94
   63},
 70
 #{96 1 98 35 99 36 5 7 39 72 41 42 74 
11 75 45 78 48 19 83 84 88 60},
 7
 #{96 2 66 36 5 37 38 70 41 10 11 12 45 79 80 82 21 23 24 57 27 59 60
   94 63},
 39
 #{64 33 65 3 35 4 6 39 72 10 43 13 14 15 80 17 50 82 51 83 54 28 31
   95},
 71
 #{1 66 35 36 68 69 70 7 42 43 12 44 76 15 47 49 81 19 51 20 84 21 54
   57 89 27 28 92 95},
 8
 #{32 96 65 34 67 37 70 72 43 12 13 45 48 50 52 21 86 55 57 89 58 90 59
   91 28 61 30 31 95},
 40 #{0 99 68 38 8 40 9 10 42 75 78 15 47 79 17 21 57 90 93 30 62 95},
 72
 #{97 99 69 6 70 71 10 42 74 76 13 77 46 49 18 19 83 52 84 21 24 63},
 9
 #{32 33 97 4 68 7 40 73 42 11 77 79 80 50 83 52 84 54 88 25 28 60 61
   62 94 63},
 41 #{0 65 97 6 7 71 72 41 10 75 12 44 13 14 46 47 17 23 93 94},
 73
 #{96 1 97 36 37 69 7 41 42 74 11 44 45 14 15 80 19 84 86 24 62 31 63
   95},
 10
 #{0 64 2 99 5 38 72 9 43 44 76 77 78 79 16 48 18 82 85 54 86 23 90
   28},
 42
 #{1 34 98 36 6 38 70 39 9 10 42 45 77 17 81 19 20 52 85 22 54 86 23 87
   56 27 93},
 74 #{0 32 33 35 36 9 73 43 45 14 47 16 48 81 18 21 53 89 61 94 95},
 11
 #{32 1 97
 66 35 67 36 38 39 73 10 43 75 12 13 45 47 49 50 83 20 85 22
   56 26 27 60 30 62 31},
 43
 #{33 34 66 3 35 67 74 44 77 80 18 82 19 83 20 53 87 57 26 58 90 91},
 75
 #{32 64 1 97 98 99 36 5 37 70 7 40 73 10 42 43 12 44 76 47 82 52 87 27
   62},
 12 #{96 33 67 36 69 39 15 79 48 18 50 20 84 86 55 58 90 59},
 44 #{3 4 5 38 41 10 12 46 78 81 18 82 20 22 54 56 25 27 91 31 95},
 76
 #{3 99 68 37 6 71 9 13 48 50 82 19 83 21 85 86 88 25 57 26 58 27 91 29
   93 31 63 95},
 13
 #{64 1 97 73 10 43 76 45 48 81 82 51 83 52 53 22 23 55 25 89 90 92 30
   62 94},
 45
 #{32 66 98 35 67 36 6 40 41 73 43 13 77 46 78 79 17 49 52 22 55 87 24
   88 89 28 61 93},
 77
 #{96 65 34 66 68 38 71 72 10 11 75 45 77 79 80 18 19 52 85 23 55 87 88
   89 58 27 59 28 61 63 95},
 14 #{96 33 34 67 99 4 8 40 41 43 75 14 47 81 19 58 27 59 93 31},
 46 #{64 96 2 3 35 67 99 5 37 71 8 73 10 75 51 85 86 55 87 88 92 94},
 78 #{2 66 37 69 40 43 45 46 16 48 50 88 25 58 90 27 91 60 29 30 63},
 15
 #{32 64 66 4 37 69 39 8 9 10 11 43 12 44 48 80 51 83 20 84 
53 86 24 56
   28 92 30 63},
 47
 #{96 35 4 5 70 72 41 73 10 11 75 13 15 80 17 81 18 82 84 85 55 87 58
   60 30},
 79 #{65 34 98 35 99 68 70 8 72 10 11 12 78 17 82 55 56 26 27 28 94},
 16
 #{0 32 96 33 65 34 98 6 70 39 40 72 10 42 75 17 53 87 56 57 92 61 30
   62},
 48
 #{65 2 34 98 70 71 72 74 12 44 78 15 16 84 25 89 26 27 91 28 93 94
   95},
 80
 #{32 1 69 6 70 71 72 73 42 74 43 77 14 16 83 53 22 24 26 58 90 91 61
   30 63},
 17
 #{96 1 2 66 98 67 4 37 70 39 71 8 9 41 10 13 78 47 16 18 50 83 20 53
   85 23 55 88 57 89 26 92 61 93 31 95},
 49 #{0 1 3 35 36 8 72 77 47 80 17 50 19 85 22 24 56 28 60 94 63},
 81
 #{0 64 96 33 97 3 5 6 38 8 41 44 76 78 47 50 51 52 54 87 24 56 57 58
   60 92 29 62 63},
 18
 #{0 32 64 96 98 35 99 4 36 37 41 43 13 45 14 78 16 49 81 50 83 53 54
   88 89 27 60 93 30 62 63},
 50 #{66 6 38 40 41 42 77 17 81 18 22 55 24 88 26 58 27 60 29 94 31},
 82
 #{0 1 34 3 35 36 7 71 40 72 74 12 77 46 47 16 18 50 82 19 51 85 22 86
   23 87 56 89 58 91 92 93 30 62 94 31 63},
 19
 #{33 97 34 99 5 70 40
 11 46 78 47 80 17 50 19 51 86 24 56 88 26 59 92
   61 30},
 51 #{0 97 2 34 5 38 70 76 14 78 47 81 18 51 83 53 55 27 92 93 31},
 83
 #{64 2 3 36 38 39 8 72 11 14 46 16 49 51 20 84 22 87 24 88 27 91 29
   31},
 20
 #{64 34 66 67 68 37 69 7 71 72 9 10 74 43 12 13 77 14 78 49 20 85 22
   54 55 24 57 59},
 52
 #{66 98 3 67 99 68 38 71 40 42 11 77 46 17 82 52 84 21 86 24 56 57 91
   61 95},
 84
 #{32 1 65 2 66 3 35 99 4 36 5 39 8 41 74 77 15 47 79 49 81 50 83 53 85
   22 55 56 88 90 59 29},
 21
 #{0 96 1 2 34 99 36 70 39 72 9 73 42 43 76 77 14 79 49 19 51 83 22 56
   89 26 92 30 31 63 95},
 53
 #{96 34 35 68 5 38 70 39 71 8 40 41 73 10 43 12 13 77 47 48 18 50 82
   19 20 52 84 85 54 55 24 57 26 60 95},
 85
 #{97 36 68 69 9 41 42 11 75 44 13 47 17 50 83 20 54 25 90 92 93 62 31
   63},
 22
 #{0 64 1 34 66 3 5 70 7 71 42 74 43 44 13 77 80 81 19 21 85 54 23 55
   56 58 27 59 91 92 30 62},
 54
 #{32 96 33 65 2 9 41 73 10 76 14 46 51 22 23 56 25 57 90 27 91 60 30
   94 95},
 86 #{0 1 34 5 70 8 41 11 43 77 78 81 53 54 87
 24 58 27 28 60 95},
 23 #{0 3 35 36 70 7 8 12 44 45 48 18 82 51 57 90 91 92},
 55 #{65 97 67 7 39 9 41 10 42 43 44 76 45 79 17 51 23 56 25 60 29 30},
 87 #{1 34 66 69 8 40 72 19 20 52 21 22 54 25 89 58 93 30 31 63},
 24
 #{33 98 67 6 39 9 42 44 13 77 81 18 50 82 19 20 21 85 22 55 87 25 57
   26 58 59 91 29 62 94 63},
 56
 #{64 65 98 67 4 36 70 40 15 79 48 80 81 84 53 85 22 88 89 26 59 60
   29},
 88
 #{96 1 97 34 98 3 4 68 5 37 6 38 41 73 10 75 44 45 15 79 16 81 82 19
   51 21 22 57 26 29 94 31},
 25
 #{64 65 97 2 36 68 7 9 10 11 44 46 16 50 82 83 20 85 86 23 87 57 26 27
   93 62},
 57 #{32 35 37 73 10 11 43 15 47 16 53 24 57 89},
 89 #{96 4 37 70 71 8 73 10 76 13 46 47 16 49 50 82 53 63},
 26
 #{0 96 1 5 37 72 73 11 46 78 17 81 18 52 54 87 88 25 89 91 60 93 63},
 58
 #{0 32 33 34 67 6 7 9 13 14 46 15 49 82 19 83 21 54 86 56 57 90 62},
 90
 #{0 33 65 2 35 99 4 6 38 71 40 9 41 74 12 14 15 50 82 84 21 87 24 26
   59 95},
 27 #{0 32 1 98 37 41 11 78 19 52 21 24 56 88 25 57 89 58 27 31 95},
 59 #{32 1 33 65 2 34
 3 68 7 39 9 10 11 76 13 81 20 85 87 58 94 31},
 91 #{0 66 4 38 8 40 41 44 45 82 51 85 22 55 25 60 30 95},
 28 #{97 98 67 36 6 40 74 76 78 47 81 18 50 19 21 22 54 88 89 29 94},
 60
 #{32 96 65 36 6 70 8 40 9 44 13 78 15 48 49 19 52 22 24 89 27 28 60 29
   61},
 92
 #{96 1 33 36 5 69 6 70 7 8 40 73 75 76 79 81 50 52 53 55 56 26 59 92
   93 95},
 29 #{97 34 3 5 37 9 41 11 76 14 16 49 85 86 24 25 59 91 30 62 94 63},
 61
 #{33 97 2 3 35 4 36 68 5 7 71 10 42 75 76 16 17 81 82 20 52 84 22 55
   87 88 57 92 94},
 93
 #{65 66 3 35 36 5 37 6 8 40 72 9 76 78 80 49 82 54 86 23 87 24 25 26
   58 27 91 29 61},
 30 #{98 40 76 79 48 81 82 19 23 87 57 61 31},
 62
 #{0 1 67 5 6 39 72 45 46 79 16 18 19 53 22 57 58 90 59 91 92 61 94},
 94 #{1 2 3 5 7 8 76 16 48 17 49 19 20 52 84 21 86 89 28 93 94},
 31
 #{32 34 35 68 5 6 38 70 7 73 42 47 79 16 80 18 82 20 53 88 58 27 59 91
   30},
 63
 #{33 97 99 70 40 74 76 15 47 49 81 51 52 84 55 87 25 58 28 92 29 94},
 95
 #{32 64 66 35 67 4 68 69 38 39 72 11 44 79 16 17 82 51 20 52 84 54 86
   88 28 93 31 63 95}}
   
=> (map count (tarjan g))
(24 24 25 25 24 75 24 51 25 25 50 29 20 21 23 48 27 21 43 38 21 36 24 42 29 77 38 26 24 28 49 22 25 29 38 43 22 43 24 21 29 28 63 29 32 32 66 18 19 44 30 21 24 24 22 44 25 18 22 21 26 22 69 22 23 27 21 26)