Para resolver el problema creamos el siguiente grafo:
cada vertice representa una mariposa, y hay una arista entre dos vertices sólo si hay un juicio
entre las mariposas que representa cada vertice. 
Haremos una distinción entre cada arista según si el juicio de los vertices es que son iguales o que son distintos.
Puede que el grafo no sea conexo,en ese caso trabajaremos con cada componente conexa por separado. 
Usaremos un arreglo L de tamaño n. donde en L[i] se encuentraran todos los nodos que estan a una distancia i de s. 
Asumimos que cada nodo es un número entre 1 y n.

Algorimto:
1)  marcar todos los nodos de G como no visitados
2)  Por cada componente conexa C de G{
3)      marcar s como visitado y asociarlo a la especie A(elegido arbitrariamente)
4)      establecer todas las listas L[i] como vacias
5)     Definimos L[0]=s
6)      establecemos el contador de capas i=0
7)      mientras L[i] no este vacio{
 8)        para cada nodo u e L[i]{
  9)           considere cada arista (u,v) incidente a u
  10)           si v no esta marcada como visitado
  11)              marcar v como visitado       
  12)              agregar v a la lista L[i+1]
  13)                 si el jucio (u,v) es "diferentes"
  14)                        asociar v  la especie opuesta de u
  15)                 else(juicio es "iguales")
  16)                        asociar v la misma especie que u
  17)              end si   
  18)         end para
  19)   end mientras       
  20    para cada arista(u,v)(
  21)     si el jucio es "iguales" y (u y v tienen diferentes especies asociadas)
  22)         hay una inconsistencia
  23)     else si el juicio es "distintas" y (u y v tienen la misma especie asociadas)
  24)         hay una inconsistencia
  25)   end para    

b)correción del algoritmo:
Veamos que si el algoritmo encuentra una inconsistencia entonces el conjunto de juicios es inconsistente.
La asignación de especies para cada vertice lo hacemos a través de una recorrida BFS, este recorrida utiliza un subconjunto de juicios
(las aristas del arbol BFS que construye implicitamente). Además, esta recorrida, es la única posible con la expeción de cambiar el nodo s de cada componente y/o cambiar A por B.
Entonces si encontramos una inconsitencia necesariamente en nuestro subconjunto de vertices,necesariamente  el conjunto de juicios total es inconsistente.

Si el conjunto de juicios es inconsitente, necesariamente el grafo que construimos es inconsitente, por lo tanto en el ciclo del paso 20 lo detectaremos y encontraremos una
inconsistencia.

c)
Para la construcición del grafo ,utilizaremos una lista de adyacencia.Esta construción es O(m+n) ya que al haber n vertices, tendremos n listas y 2m nodos en total de todas las listas, ya que hay m aristas y cada una aparece en 2 listas.
Para saber si un nodo fue explorado utilizaremos un arreglo descubierto que indicará si fue explorado o no.
Para saber que especie tiene asignada también usaremos un arreglo especies con dos posibles valores, A y B.
El for del paso 9, para cada nodo u, la cantidad total de iteraciones será la cantidad de aristas adyacentes a él, justamente su grado.
Todos los pasos que estan dentro de este bucle, llevan tiempo constante, ya que son inserciones en una lista(las podemos hacer al principio) y asignaciones en arreglos. 
Entonces para cada nodo u el tiempo del bucle del paso 9 es O(nv). 
Entonces el tiempo total sobre todos los nodos es O(sumatoria todos los grados de cada vertice)=O(2m).
A su vez necesitamos O(n) de tiempo para incializar  los arreglos
entonces el tiempo total desde la linea 1 hasta la 19 es O(m+n).

El for del paso 20, como tenemos m aristas, no se repetirá mas de m veces, y las instrucciones dentro de este bucle son de tiempo constante ya que es comparar dos elementos de un arreglo, entonces el tiempo total es O(m)

Por lo tanto el tiempo total del algoritmo es O(m+n)+O(m+n)+O(m)=O(m+n).