algorithm - Calculate the number of nodes on either side of an edge in a tree -


a tree here means acyclic undirected graph n nodes , n-1 edges. each edge in tree, calculate number of nodes on either side of it. if on removing edge, 2 trees having a , b number of nodes, want find values a , b edges in tree (ideally in o(n) time).

intuitively feel multisource bfs starting "leaf" nodes yield answer, i'm not able translate code.

for credit, provide algorithm works in general graph.

run depth-first search (or breadth-first search if more) node. node called root node, , edges traversed in direction root node.

for each node, calculate number of nodes in rooted subtree. when node visited first time, set number 1. when subtree of child visited, add size of subtree parent.

after this, know number of nodes on 1 side of each edge. number on other side total minus number found.

(the credit version of question involves finding bridges in graph on top of non-trivial part, , deserves asked separate question if interested.)


Comments

Post a Comment

Popular posts from this blog

aws api gateway - SerializationException in posting new Records via Dynamodb Proxy Service in API -

i getting "__type": "com.amazon.coral.service#serializationexception" as reply in postman & in test console in api gateway trying post record directly dynamodb using api proxy services.. referring aws article - https://aws.amazon.com/blogs/compute/using-amazon-api-gateway-as-a-proxy-for-dynamodb/ here's mapping { "tablename": "tablenamegoeshere", "item": { "id" : "$context.requestid" "eventname" : "$input.path('$.eventname')", "timestamp" : $input.path('$.timestamp'), "answers": "$util.parsejson($input.path('$.answers'))" } } update: did asked ... , worked if try add array of json objects gives me above same error - here's trying now. please - couldnt find on google well #set($inputroot = $input.path('$')) { "tablename": "answer", "item": {
Read more

asp.net - Problems sending emails from forum -

i have been redesigning site has message board, has been written guy looked after site. it has few problems , written in .asp , uses .mdb files database. you can see whole thing here . feel free post if helps, test thing have set using original files , new database. the basic problem when posts message, supposed email sent them, have posted it. when replies, originator supposed message, replier has been posted. i’d have thought @ point in process there should script/file in postmessage.asp? the postmessage.asp page below. <% option explicit %> <!-- #include virtual="common/adovbs.inc" --> <html> <head> <meta http-equiv="content-type" content="text/html; charset=windows-1252"> <meta name="generator" content="microsoft frontpage 4.0"> <meta name="progid" content="frontpage.editor.document"> <title>new page 2</title> <base target="_self"
Read more