algorithm - Printing out nodes in a disjoint-set data structure in linear time -


i'm trying exercise in introduction algorithms cormen et al has disjoin set data structure:

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. assume can print each member of set in o(1) time.

now, i'm quite sure attribute needed tail pointer, can keep track of children.

since disjoint set structure has parent attribute, find-set(x) can print out nodes going in 1 direction. now, having tail pointer, let's go other direction well.

however, i'm not sure how write algorithm this. if me out in pseudocode, appreciated.

each node should have next pointer next node in set in. nodes in set should form circular linked list.

when singleton set first created, node's next pointer points itself.

when merge set node x , set node y (and you've checked sets different normalizing set representatives), merge circular linked lists, can swapping x.next , y.next; o(1) operation.

to list elements in set containing node x, traverse circular linked list starting x.


Comments

Post a Comment

Popular posts from this blog

apache - Remove .php and add trailing slash in url using htaccess not loading css -

i have add following code htaccess file removing .php extension , add trailing slash urls. worked fine reduced page loading speed , css code not loading @ all. pages ugly. please help rewriteengine on rewritebase / ## hide .php extension snippet # externally redirect /dir/foo.php /dir/foo rewritecond %{the_request} ^[a-z]{3,}\s([^.]+)\.php [nc] rewriterule ^ %1/ [r,l] # add trailing slash rewritecond %{request_filename} !-f rewritecond %{request_uri} !/$ rewriterule . %{request_uri}/ [l,r=301] # internally forward /dir/foo /dir/foo.php rewritecond %{request_filename} !-d rewritecond %{request_filename}.php -f rewriterule ^(.*?)/?$ $1.php [l] we can rewrite urls using .htaccess files. before writing in .htaccess files need verify kind of server using. can check server adding a <?php phpinfo(); ?> in php page. ensure mod_rewrite module enabled in apache server. can identified checking phpinfo included page. common methods used url rewriting follows ...
Read more

javascript - jQuery show full size image on click -

pretty self explanatory not workking . i want display full image when user click on image... yes know there tons of plugins but i want keep simple. any idea ? css : .full { display: none; width: 500px; height: 500px; margin-left: 100px; margin-top: -300px; position: fixed; background-color: #f00; z-index: 6; } .thumbnail { width: 50px; height: 50px; } html: <img class="thumbnail" src="http://4.bp.blogspot.com/-uhbdp2esxng/txneptvi92i/aaaaaaaaaky/upfqis7zto0/s1600/rihanna-wallpaper.jpg"> jquery: $(document).ready(function() { $('.thumbnail').on('click', function() { var img = $('<img />',{src:this.src,'class':'full'}); $('.full').html(img).show(); console.log('done!'); }); }); try looking how jquery works. $(document).ready(function() { $('.thumbnail').on('click', function(...
Read more