{"id":34172,"date":"2023-03-02T14:56:42","date_gmt":"2023-03-02T09:26:42","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/"},"modified":"2023-03-02T14:56:42","modified_gmt":"2023-03-02T09:26:42","slug":"solved-a-program-which-is-difficult","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/","title":{"rendered":"[Solved] A program which is difficult"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

Essentially, your question is this:
\ngiven a graph with nodes represented as indices and edges as index pairs,
\nand given an index i that represents a node,
\nfind all nodes which are connected to the given node.<\/p>\n

UnionFind algorithm to find connected components over nodes with indices:<\/p>\n

Initialize an array father of size number of nodes, with father[i] = i\n\nfor each edge e consisting of two indices i, j:\n    ind = i\n    while(ind != father[ind]) ind = father[ind]\n    father[j] = ind\n\nfor each entry i of the array:\n    replace father[i] by father[father[i]] until those are equal\n<\/code><\/pre>\n
After that, all nodes in the same component have the same father. You do that with your data, and then, for a given index i, find all other indices j with father[i] = father[j].<\/p>\n
(slight improvement in run time: after ind is set to it’s final value, update the father of i and its father and so on to the value ind)<\/p>\n
Short explanation of UnionFind: it creates a tree in which only index pointers to the father of a node is stored (requires only an array). This is done by iterating over the edges. For every edge, the father of one of the incident nodes is set to the highest ancestor of the other node. Essentially, we start with a forest of single nodes and assemble them to trees. At the end, we change the remaining trees so that all leaves are direct children of the root.<\/p>\n
Since in your example some numbers are missing, you might want to create some table that translates your input index to a range of numbers which are actually used. However, if we are talking about a small maximum index, like under one thousand, it won’t really hurt not to do it.<\/p>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            <\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved A program which is difficult <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] Essentially, your question is this: given a graph with nodes represented as indices and edges as index pairs, and given an index i that represents a node, find all nodes which are connected to the given node. UnionFind algorithm to find connected components over nodes with indices: Initialize an array father of size number … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,324,494],"class_list":["post-34172","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-c","tag-recursion"],"yoast_head":"\n[Solved] A program which is difficult - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] A program which is difficult - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] Essentially, your question is this: given a graph with nodes represented as indices and edges as index pairs, and given an index i that represents a node, find all nodes which are connected to the given node. UnionFind algorithm to find connected components over nodes with indices: Initialize an array father of size number ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2023-03-02T09:26:42+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] A program which is difficult\",\"datePublished\":\"2023-03-02T09:26:42+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\"},\"wordCount\":263,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"c++\",\"recursion\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\",\"name\":\"[Solved] A program which is difficult - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2023-03-02T09:26:42+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] A program which is difficult\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] A program which is difficult - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] A program which is difficult - JassWeb","og_description":"[ad_1] Essentially, your question is this: given a graph with nodes represented as indices and edges as index pairs, and given an index i that represents a node, find all nodes which are connected to the given node. UnionFind algorithm to find connected components over nodes with indices: Initialize an array father of size number ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/","og_site_name":"JassWeb","article_published_time":"2023-03-02T09:26:42+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] A program which is difficult","datePublished":"2023-03-02T09:26:42+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/"},"wordCount":263,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","c++","recursion"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/","url":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/","name":"[Solved] A program which is difficult - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2023-03-02T09:26:42+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-a-program-which-is-difficult\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] A program which is difficult"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/34172","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=34172"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/34172\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=34172"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=34172"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=34172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}