This is the question i am trying to solve: https://open.kattis.com/problems/abinitio
This is my logic. I will represent the graph using a 2d adjacency matrix. adj[i][x] represents if there is a directed connection from i to x. And I also hold two booleans values. "transposed", and "complmented". So this is how I will handle the queries. My logic is that transposing or complementing the graph twice (no matter the updates in between) will always be the same as not complementing or transposing at all. So when I want to detect whether or not there is an edge between two nodes, u, v. If the graph is transposed, I will check adj[v][u] == complemented^1. Otherwise I will check adj[u][v] = complemented^1. (If complemented is 1, i am looking for 0 and vice versa).
So this is the code I produced: https://pastebin.com/Khp01P70
However, I get WA on testcase 4. Can someone please help me debug this? Thanks in advance.
When adding a new vertex to the graph, we must consider whether the array is currently in its complement state or not. As all new vertices should not have connections to any other vertex, if the array is in its complement state, and we add a vertex x, adj[i][x] and adj[x][i] should equal 1 for all i < new size of the matrix. This is done to disconnect the vertices in the complement state.