Encontrando nós adjacentes

Um grafo é um conjunto de nós e arestas que conectam esses nós.

Os grafos podem ser direcionados ou não direcionados. Em um grafo não direcionado, uma aresta funciona nos dois sentidos, como uma rua de mão dupla. Em um grafo direcionado, cada aresta tem sua própria direção, como uma rua de mão única. Dois nós são adjacentes quando uma aresta os conecta.

Uma matriz de adjacência representa um grafo com n nós por meio de uma matriz n × n. O valor na linha i e na coluna j é 1 quando os nós i e j são adjacentes, e 0 caso contrário. Para o grafo acima, a matriz é:

int[][] graph = {
  new[] { 0, 1, 0, 0 },
  new[] { 1, 0, 1, 1 },
  new[] { 0, 1, 0, 1 },
  new[] { 0, 1, 1, 0 }
};

A primeira linha indica que o nó 0 se conecta ao nó 1, mas não a si mesmo nem aos nós 2 ou 3. A segunda linha indica que o nó 1 se conecta aos nós 0, 2 e 3, mas não a si mesmo. A terceira linha indica que o nó 2 se conecta aos nós 1 e 3, enquanto a quarta indica que o nó 3 se conecta aos nós 1 e 2. Como esse grafo não é direcionado, a matriz é simétrica em relação à sua diagonal principal.

Retorne se os dois nós fornecidos são adjacentes no grafo não direcionado representado pela matriz.

Exemplos

int[][] graph = {
  new[] { 0, 1, 0, 0 },
  new[] { 1, 0, 1, 1 },
  new[] { 0, 1, 0, 1 },
  new[] { 0, 1, 1, 0 }
};

Program.IsAdjacent(graph, 0, 1); // true
Program.IsAdjacent(graph, 0, 2); // false

int[][] graph2 = {
  new[] { 0, 1, 0, 1, 1 },
  new[] { 1, 0, 1, 0, 0 },
  new[] { 0, 1, 0, 1, 0 },
  new[] { 1, 0, 1, 0, 1 },
  new[] { 1, 0, 0, 1, 0 }
};

Program.IsAdjacent(graph2, 0, 3); // true
Program.IsAdjacent(graph2, 1, 4); // false

Notas

• A matriz é quadrada, contém apenas 0 e 1 e representa um grafo não direcionado.
• Os índices dos dois nós são válidos.
• Os grafos podem conter até 25,000 nós.
• Limite de tempo: 100 milissegundos.