際際滷

際際滷Share a Scribd company logo

Codeforces round #310 Div.1 E. Case of Computer Network

Download as PPTX, PDF
M
minsu kim

This document describes an algorithm for determining if a directed path exists between pairs of vertices in an undirected graph. It involves decomposing the graph into biconnected components, which can be directed circularly. It then treats the decomposed graph as a forest, finds the lowest common ancestor of each vertex pair, and assigns directions upwards or downwards to ensure the pairs are connected. The implementation counts the number of vertices above and below the lowest common ancestor to determine the edge direction without using heavy-light decomposition.

1 of 9
Download to read offline
Codeforces Round #310(Div.1) E. Case of Computer Network Minsu Kim
Description Given an undirected graph G=(V,E) allowing multiple edges and pairs of vertices M, Check if there exists a proper direction of E that makes every path uv in M reachable. |V|, |E|, |M| < 2*10^5
Bi-connected Components Decomposition In a bi-connected component, we can make a circular direction This allows any paths in this component reachable!
Bi-connected Components Decomposition In a bi-connected component, we can make a circular direction v u This allows any paths in this component reachable!
Bi-connected Components Decomposition In a bi-connected component, we can make a circular direction u v This allows any paths in this component reachable!
Bi-connected Components Decomposition Use Tarjans algorithm to decompose the initial graph. Then, the decomposed graph is unrooted forest.
Assigning direction For each (u,v) in M If u and v arent in the same component : no solution Otherwise, for an arbitrary root r in the tree, find the LCA called l. Path ul should be directed upwards. Path lv should be directed downwards. If there exists any contradiction : no solution
Implementation How to assign the direction of all the edges in the path? Heavy-Light Decomposition with path update can be a solution But theres a simpler way
Implementation Iterating each vertex in reversed-preorder, assign the direction of the edge towards its parent: Summing up 3 kinds of vertex count in this subtree: a = beginning vertex, b = ending vertex, c = passing vertex(chosen as LCA) IF a>c , the edge should be directed upwards. (there exists a vertex in this subtree who wants to go out of this subtree) IF b>c, the edge should be directed downwards. (there exists a vertex out of this subtree who wants to go inside this subtree) IF a>c and b>c, CONTRADICTION!

More Related Content

Codeforces round #310 Div.1 E. Case of Computer Network

  • 1. Codeforces Round #310(Div.1) E. Case of Computer Network Minsu Kim
  • 2. Description Given an undirected graph G=(V,E) allowing multiple edges and pairs of vertices M, Check if there exists a proper direction of E that makes every path uv in M reachable. |V|, |E|, |M| < 2*10^5
  • 3. Bi-connected Components Decomposition In a bi-connected component, we can make a circular direction This allows any paths in this component reachable!
  • 4. Bi-connected Components Decomposition In a bi-connected component, we can make a circular direction v u This allows any paths in this component reachable!
  • 5. Bi-connected Components Decomposition In a bi-connected component, we can make a circular direction u v This allows any paths in this component reachable!
  • 6. Bi-connected Components Decomposition Use Tarjans algorithm to decompose the initial graph. Then, the decomposed graph is unrooted forest.
  • 7. Assigning direction For each (u,v) in M If u and v arent in the same component : no solution Otherwise, for an arbitrary root r in the tree, find the LCA called l. Path ul should be directed upwards. Path lv should be directed downwards. If there exists any contradiction : no solution
  • 8. Implementation How to assign the direction of all the edges in the path? Heavy-Light Decomposition with path update can be a solution But theres a simpler way
  • 9. Implementation Iterating each vertex in reversed-preorder, assign the direction of the edge towards its parent: Summing up 3 kinds of vertex count in this subtree: a = beginning vertex, b = ending vertex, c = passing vertex(chosen as LCA) IF a>c , the edge should be directed upwards. (there exists a vertex in this subtree who wants to go out of this subtree) IF b>c, the edge should be directed downwards. (there exists a vertex out of this subtree who wants to go inside this subtree) IF a>c and b>c, CONTRADICTION!
AboutCopyright
息 2025 際際滷