algorithm - Union-Find: retrieve all members of a set efficiently -

-

i'm working union-find algorithm. in first part of program, algorithm computes partition of big set e.

after that, want retrieve members of set s, contains given node x.

until now, naively, testing membership of elements of e set s. yesterday reading "introduction algorithms" (by clrs, 3rd edition, ex. 21.3-4), and, in exercises, found that:

suppose wish add operation print-set(x), given node x , prints members of x's set, in order. show how can add single attribute each node in disjoint-set forest print-set(x) takes time linear in number of members of x's set, , asymptotic running times of other operations unchanged.

"linear in number of members of x's set" great improvement problem! so, i'm trying solve exersice... , after unsuccessful tries, i'm asking on stack overflow!

recall union-find implemented upside-down tree, each set s = {v1, v2, ..., vn}, have vn - 1 edges, have same root (or sink).

now, whenever add edge (vi, vj) tree, add edge (using new attribute) (vj, vi). , when remove node, remove attribute well.

note new edge separated old one. use only when printing elements in set. , modify whenever original edge modified in original algorithm.

note attribute list of nodes, total number of elements in lists combined still n - 1.

this give second tree, not upside down. now, using root, , doing tree-traversal (using e.g. bfs or dfs), can print elements.


Comments

Post a Comment

Popular posts from this blog

windows - Single EXE to Install Python Standalone Executable for Easy Distribution -

-
i used pyinstaller create standalone exe file pyqt project. did not use single file option because exe created single file option takes long open. therefore, pyinstaller created dist folder contains bunch of files including program.exe file. create setup.exe file place contents of dist folder in program directory , create shortcut in start menu , on desktop. want super simple user. maybe setup.exe files when download program cnet. found inno-setup, looks promising. however, not know if there special considerations because program standalone program create python/pyqt program. thanks! have experience task? there program using task not know about? inno-setup or nsis easiest use. tell them files include , put them , create nice installer you. wrote short tutorial on experiences using innosetup might find helpful: http://www.blog.pythonlibrary.org/2008/08/27/packaging-wxpymail-for-distribution/ note tutorial based around wxpython app wrote, concepts same.
Read more

c# - Access objects in UserControl from MainWindow in WPF -

-
i have simple xaml, how can change text property of textblock in usercontrol1 mainwindow ? <window x:class="refactorxaml.mainwindow" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" xmlns:refactorxaml="clr-namespace:refactorxaml" title="mainwindow" height="350" width="525"> <grid> <grid.rowdefinitions> <rowdefinition height="100"></rowdefinition> <rowdefinition height="100"></rowdefinition> </grid.rowdefinitions> <grid> <refactorxaml:usercontrol1></refactorxaml:usercontrol1> </grid> <grid grid.row="1"> <button>change text</button> </grid> </grid> </window> <usercon...
Read more

javascript - How to name a jQuery function to make a browser's back button work? -

-
i'm trying write function ajaxyfy web site, works perfect, except function button. that's have now: function loading() { if (typeof history.pushstate !== "undefined") { var historycount = 0; $('.menu-item, .logo').on('click','a',function(e){ e.preventdefault(); $(this).data('clicked', true); if ($(this).is('.logo a')) { var homepage = $(this).attr('href'); function1(homepage); history.pushstate(null, null, homepage); } else if ($(this).is('.projects a')) { var projects = $(this).attr('href'); function2(projects); history.pushstate(null, null, projects); } else { var pages = $(this).attr('href'); function3(pages); history.pushstate(null, null, pages); ...
Read more