Related to the below: there are no reasons IGraph is not preloaded.

Is it intended that the passed in array be modified in place? That's what the top solutions are doing. Typically this is considered bad practice. Given that the method has a return value, one would assume that this is an oversight. Maybe the description could explicitly state that this shouldn't be done (if that is intended).

Your IGraph/Graph doesn't even implement IEqualityComparer or IEquatable. How are you going to determine if two nodes are the same then?

We're not provided the total amount of nodes in the graph.

What if there are more than one connected components?

Needs random tests

Duplicate:

https://www.codewars.com/kata/search/?q=tic+tac+toe&beta=false

Testing for every outcome at least once in the standard test cases would be nice. One can write his own test cases, true, but it's better to have the obvious tests there from the beginning.