Hi, can anybody give a hint how to solve this problem?

Floyd.

Notice that if there is an edge between i and j then a[i][j] + a[j][i] <= 1 (a is input array). The reverse is not true, but you no need to worry as unnecessary edges do not change the array a. So you have a graph, run Floyd to check if it matches with array a.