// http://groups-beta.google.com/group/comp.lang.functional/browse_thread/thread/8383429f1d74814c/3559160bd1efa730?hl=en#3559160bd1efa730

/dense:

d:(|/1<+/){x . 2#,1_>+/x}\

D:(1 0 0 1 0 0 
   0 1 0 1 1 1
   0 0 1 0 0 1
   1 1 0 1 0 0 
   0 1 0 0 1 0
   0 1 1 0 0 1)

d D

/sparse:

s:(~~/){x@\:,/g 1_>#:'g:=*x}\

S:(&+/'S;,/&:'S:D&~(!#D)>\:/:!#D)       / U[0;i] has neighbor U[1;i]

s S

/super-sparse:

p:(~&/~/')(1_)\

P:+P@\:>#:'*|P:(+,?*S;S[1;=S[0]])       / P[i;0] has neighbors P[i;1]

p P

/but (without sorting) this is just:

Q:+(+,?*S;S[1;=S[0]])                   

Q@&~/'Q  

\

  d D
((1 0 0 1 0 0
  0 1 0 1 1 1
  0 0 1 0 0 1
  1 1 0 1 0 0
  0 1 0 0 1 0
  0 1 1 0 0 1)
 (1 0 1 0 0
  0 1 0 1 0
  1 0 1 0 0
  0 1 0 1 0
  0 0 0 0 1)
 (1 0 1 0
  0 1 0 0
  1 0 1 0
  0 0 0 1)
 (1 0 0
  0 1 0
  0 0 1))

  s S
((0 1 2 3 3 3 4 4 5 5 5
  0 1 2 0 1 3 1 4 1 2 5)
 (0 1 2 4 4 5 5 5
  0 1 2 1 4 1 2 5)
 (0 1 2 4 4
  0 1 2 1 4)
 (0 1 2
  0 1 2))

  p P
(((,3
   0 1 3)
  (,5
   1 2 5)
  (,4
   1 4)
  (,0
   ,0)
  (,1
   ,1)
  (,2
   ,2))
 ((,5
   1 2 5)
  (,4
   1 4)
  (,0
   ,0)
  (,1
   ,1)
  (,2
   ,2))
 ((,4
   1 4)
  (,0
   ,0)
  (,1
   ,1)
  (,2
   ,2))
 ((,0
   ,0)
  (,1
   ,1)
  (,2
   ,2)))

  Q@&~/'Q  
((,0
  ,0)
 (,1
  ,1)
 (,2
  ,2))