Lance_HAOH's blog

By Lance_HAOH, history, 10 months ago, In English,

Hi. I am trying to solve this problem.

For convenience, I have summarized the problem statement below (based on my understanding):

Given a directed graph with N vertices and E edges (with cycles and not necessarily connected), find the minimum number of edges that we need to retain such that connectivity between vertices is retained as given in the original graph.

Input size: 1 ≤ N, E ≤ 2e5
Time limit: 1s

For example, for the following graph:

graph

We should retain the edges:

0 -> 1
1 -> 2
1 -> 3

So we must use a minimum of 3 edges.

Note that:
0 -> 2 is redundant as we can use the path 0 -> 1 -> 2 to get from 0 to 2.
0 -> 3 is redundant as we can use the path 0 -> 1 -> 3 to get from 0 to 3. (Thanks filippos for catching this mistake!)

This problem seems to be asking for the transitive reduction of a graph which can only be found in at least O(n2) based on what I found on Google and this clearly wouldn't pass the time limit. Furthermore, the list of AC solutions suggests that there is a linear time solution to this problem.

Could someone please advise me on how to solve this problem?

UPD Managed to solve this problem (thank you yosei-san for your incredible patience and explanation!).

I indeed had a wrong understanding of this problem and overly constrained it.

For readers who are looking for the solution to this problem, I have posted my solution below:

My approach
My accepted code
 
 
 
 
  • Vote: I like it  
  • +14
  • Vote: I do not like it  

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think that answer to the given input should be 3 instead of 4 as we don't need 0 -> 3 as we can use 0 -> 1 -> 3 :)

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ah. You are right! Sorry for my slip-up. I have updated the sample.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Lance_HAOH (previous revision, new revision, compare).

»
10 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I think you're trying to solve another problem than the one described in the link. You can build any graph you want as long as it satisfies the conditions. Your interpretation constrains the task and makes it a lot harder.

Think about line graphs and cycles, and about topological sorting.

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I'm sorry but I couldn't catch your hint. Yeah. I think there must be some way to do it without finding transitive reduction. But I cannot visualize how to use topological sort for this problem.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Let's look at the connected components in our graph.

      If a component is a DAG, then place the nodes in a line in the order of their topological sort. Otherwise place all the nodes in a cycle.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Lance_HAOH (previous revision, new revision, compare).