Assume we have a digraph, it is not a complete graph and has more than one SCC. I wonder if the patterns of Strongly Connected Component changes if we transpose the graph and use Kosaraju's Algorithm? By saying "transpose the graph" I mean flip the direction of edges. If we try to find SCC in the transposed/reversed graph instead of the original, will the SCC we find be different?
I came up with this question as I misunderstood the algorithm of SCC and runs it on my transposed/reversed graph. What I got is identical SCC to the correct answer/which runs Kosaraju's algorithm. Is it universally true to all graphs?
No the SCC of the graph will remain the same even when the graph is reversed and that is very important point in kosaraju's algorithm for SCC's. Only the links between SCC's are reversed. Kosaraju's algorithm leverages this fact to evaluate DFS on reversed graph which now gives higher finish time values for SCC's which are closer to the sink SCC. As Sink SCC has no outgoing edge to another SCC hence evaluating DFS on it gives out the SCC as whole connected component and also allows decomposition of graph into a subgraph with similar properties on which we again apply DFS to get another SCC.