What should be the approach to find all paths with maximum flow? The graph is directed acyclic graph and the maximum number of nodes(vertices) in the graph can be 40 and edges around 80. Also, most of the edges have unit capacity.

# | User | Rating |
---|---|---|

1 | tourist | 3748 |

2 | Benq | 3540 |

3 | Petr | 3470 |

4 | Radewoosh | 3355 |

5 | ecnerwala | 3347 |

6 | maroonrk | 3345 |

7 | jiangly | 3324 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 200 |

2 | Errichto | 197 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

5 | awoo | 185 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 175 |

9 | -is-this-fft- | 173 |

9 | antontrygubO_o | 173 |

Help needed in the following problem :

There are **N** (1<=N<=200000) line segments (end-point coordinates are positive integers less than **1e9**). The task is to merge the line segments that are * overlapping* and finally print the coordinates of all the merged line-segments.

Sample Test Case

N = 4

Line segments:

[(1,1) (5,1)]

[(4,1) (7,1)]

[(3,3) (9,3)]

[(5,3) (8,3)]

The answer for this test case would be :

[(1,1) (7,1)]

[(3,3) (9,3)]

**My Approach** : Consider each line segment as a vertex and make edges between segments U and V if U and V overlaps. Then, find the connected components. For each connected components, answer can be calculated by taking the min of left coordinates and maximum of right coordinates. But this approach is O(N^2) and will not work for N=200000.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/26/2021 07:22:13 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|