{"id":24166,"date":"2022-11-30T20:26:12","date_gmt":"2022-11-30T14:56:12","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/"},"modified":"2022-11-30T20:26:12","modified_gmt":"2022-11-30T14:56:12","slug":"solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/","title":{"rendered":"[Solved] Determine if there is a path between all vertex pairs on an directed graph"},"content":{"rendered":"

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

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

The following algorithm can me implemented with O(N+M)<\/code> complexity.<\/p>\n

    \n
  1. \n

    Take any vertex u<\/code>. Use flood fill<\/a> algorithm to reach other vertices. If any vertex is not reachable, return NOK<\/code>.<\/p>\n<\/li>\n

  2. \n

    Now do the same, but go to the opposite direction. If any vertex is not reachable, return NOK<\/code>.<\/p>\n<\/li>\n

  3. \n

    Return OK<\/code>. (Here we know that there is a path from any vertex v<\/code> to u<\/code> because of [2], and there is a path from u<\/code> to any vertex w<\/code> because of [1].)<\/p>\n<\/li>\n<\/ol><\/div>\n

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

    <\/span> <\/p><\/div>\n<\/div>\n

    [ad_2]<\/p>\n

    solved Determine if there is a path between all vertex pairs on an directed graph <\/p>\n","protected":false},"excerpt":{"rendered":"

    [ad_1] The following algorithm can me implemented with O(N+M) complexity. Take any vertex u. Use flood fill algorithm to reach other vertices. If any vertex is not reachable, return NOK. Now do the same, but go to the opposite direction. If any vertex is not reachable, return NOK. Return OK. (Here we know that there … 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,5136,5137],"class_list":["post-24166","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-c","tag-graph-theory","tag-undirected-graph"],"yoast_head":"\n[Solved] Determine if there is a path between all vertex pairs on an directed graph - 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-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Determine if there is a path between all vertex pairs on an directed graph - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The following algorithm can me implemented with O(N+M) complexity. Take any vertex u. Use flood fill algorithm to reach other vertices. If any vertex is not reachable, return NOK. Now do the same, but go to the opposite direction. If any vertex is not reachable, return NOK. Return OK. (Here we know that there ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-11-30T14:56:12+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<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Determine if there is a path between all vertex pairs on an directed graph\",\"datePublished\":\"2022-11-30T14:56:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\"},\"wordCount\":101,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"c++\",\"graph-theory\",\"undirected-graph\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\",\"name\":\"[Solved] Determine if there is a path between all vertex pairs on an directed graph - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-11-30T14:56:12+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Determine if there is a path between all vertex pairs on an directed graph\"}]},{\"@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=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Determine if there is a path between all vertex pairs on an directed graph - 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-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Determine if there is a path between all vertex pairs on an directed graph - JassWeb","og_description":"[ad_1] The following algorithm can me implemented with O(N+M) complexity. Take any vertex u. Use flood fill algorithm to reach other vertices. If any vertex is not reachable, return NOK. Now do the same, but go to the opposite direction. If any vertex is not reachable, return NOK. Return OK. (Here we know that there ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/","og_site_name":"JassWeb","article_published_time":"2022-11-30T14:56:12+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Determine if there is a path between all vertex pairs on an directed graph","datePublished":"2022-11-30T14:56:12+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/"},"wordCount":101,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","c++","graph-theory","undirected-graph"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/","url":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/","name":"[Solved] Determine if there is a path between all vertex pairs on an directed graph - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-11-30T14:56:12+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-determine-if-there-is-a-path-between-all-vertex-pairs-on-an-directed-graph\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Determine if there is a path between all vertex pairs on an directed graph"}]},{"@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=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","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\/24166","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=24166"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/24166\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=24166"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=24166"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=24166"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}