Nós adjacentes (grafo direcionado)

Um grafo direcionado é como um grafo não direcionado, exceto pelo fato de que cada aresta tem uma direção que vai de um nó de origem até um nó de destino.

Neste grafo, o nó 0 é adjacente ao nó 1, mas o nó 1 não é adjacente ao nó 0. Se o grafo não fosse direcionado, ele seria assim:

Em um grafo direcionado, inverter uma aresta cria um grafo diferente:

A matriz de adjacência de um grafo não direcionado é simétrica em relação à sua diagonal principal, mas a matriz de adjacência de um grafo direcionado não precisa ser. Um 1 na linha i, coluna j, significa que há uma aresta do nó i até o nó j.

O grafo da imagem pode ser representado por esta matriz de adjacência:

std::vector<std::vector<int>>{{0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 0, 0}}

O nó 1 não tem arestas de saída, portanto sua linha contém apenas zeros. Um nó sem arestas de entrada teria uma coluna contendo apenas zeros.

Instruções

Dadas a matriz de adjacência de um grafo direcionado e duas posições válidas de nós, retorne se o primeiro nó é adjacente ao segundo. Verifique a célula que fica na linha do nó de origem e na coluna do nó de destino; a direção é importante.

Exemplos

adjacent(std::vector<std::vector<int>>{{0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 0, 0}}, 0, 1) // true
adjacent(std::vector<std::vector<int>>{{0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 0, 0}}, 1, 0) // false

Notas

• Os grafos podem ter até 25,000 nós.
• O limite de tempo é de 100 milissegundos, portanto verifique apenas a célula solicitada.