亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        Tarjan算法在程序設(shè)計(jì)競(jìng)賽中的應(yīng)用探析

        2023-06-10 12:41:51郭涵濤毛玉萃
        電腦知識(shí)與技術(shù) 2023年12期
        關(guān)鍵詞:實(shí)例

        郭涵濤 毛玉萃

        關(guān)鍵詞:Tarjan;程序類競(jìng)賽;實(shí)例

        中圖分類號(hào):TP311.52 文獻(xiàn)標(biāo)識(shí)碼:A

        文章編號(hào):1009-3044(2023)12-0029-05

        1 Tarjan 算法簡(jiǎn)述[1]

        Tarjan 算法是基于深度優(yōu)先搜索的算法,由著名計(jì)算機(jī)科學(xué)家Robert Tarjan發(fā)明,用于求解圖的連通性問題。Tarjan 算法可以在線性時(shí)間內(nèi)求出無向圖的割點(diǎn)與橋,進(jìn)一步地可以求解無向圖的連通分量;也可以求解有向圖的強(qiáng)連通分量、必經(jīng)點(diǎn)與必經(jīng)邊;該算法是圖論中非常實(shí)用且常用的算法之一,能解決強(qiáng)連通分量,雙連通分量,割點(diǎn)和橋,以及求最近公共祖先(LCA) 等問題。

        1.1 Tarjan 問題中的概念介紹

        割點(diǎn):如果一個(gè)節(jié)點(diǎn)X和所有與X關(guān)聯(lián)的邊從圖中刪除后,圖會(huì)被分割成兩個(gè)或兩個(gè)以上不相連的子圖,那么這個(gè)分割點(diǎn)就叫作X。

        割邊:如果把圖中的邊e去掉后,圖就會(huì)被分割成兩個(gè)不相連的子圖,那么這條邊或者叫切邊或者叫割邊。

        時(shí)間戳:時(shí)間戳是用來標(biāo)記圖中每個(gè)節(jié)點(diǎn)在進(jìn)行深度優(yōu)先搜索時(shí)被訪問的時(shí)間順序,用dfn[x]來表示。

        搜索樹:在無向圖中,從某一個(gè)節(jié)點(diǎn)x 出發(fā)進(jìn)行深度優(yōu)先搜索,每一個(gè)節(jié)點(diǎn)只訪問一次,所有被訪問過的節(jié)點(diǎn)與邊構(gòu)成一棵樹,稱之為“無向連通圖的搜索樹”。

        追溯值:追溯值用來表示從當(dāng)前節(jié)點(diǎn)x 作為搜索樹的根節(jié)點(diǎn)出發(fā),能夠訪問到的所有節(jié)點(diǎn)中,時(shí)間戳最小的值,用low[x]來表示。所有節(jié)點(diǎn)包含:

        1) 以x為根的搜索樹的所有節(jié)點(diǎn)。

        2) 通過一條非搜索樹上的邊,能夠到達(dá)搜索樹的所有節(jié)點(diǎn)。

        1.2 Tarjan 算法的原理[1]

        Tarjan 算法是一種利用深度優(yōu)先搜索實(shí)現(xiàn)的圖算法,它能夠?qū)D中的節(jié)點(diǎn)按照強(qiáng)連通分量進(jìn)行劃分,并將同一強(qiáng)連通分量中的節(jié)點(diǎn)放在一起。在搜索過程中,將未處理的節(jié)點(diǎn)加入一個(gè)棧中,并在回溯的過程中檢查棧頂?shù)綏V械墓?jié)點(diǎn)是否構(gòu)成了一個(gè)強(qiáng)連通分量。因此,每個(gè)強(qiáng)連通分量對(duì)應(yīng)于深度優(yōu)先搜索樹中的一棵子樹。

        算法:

        1) 當(dāng)首次搜索到點(diǎn)u時(shí)dfn[u]=low[u]=time;

        2) 每當(dāng)搜索到一個(gè)點(diǎn),把該點(diǎn)壓入棧頂;

        3) 當(dāng)u和v有邊相連時(shí):

        當(dāng)節(jié)點(diǎn)v不在棧中時(shí)(即遇到樹枝邊),執(zhí)行dfs(v) 操作,并將low[u]的值更新為min{low(u), low(v)};當(dāng)節(jié)點(diǎn)v在棧中時(shí)(即遇到前向邊或后向邊),將low[u]的值更新為min{low[u], dfn[v]}。

        4) 當(dāng)一個(gè)節(jié)點(diǎn)u的dfn值等于其low值時(shí),意味著它所在的強(qiáng)連通分量已經(jīng)被完全探索并且已經(jīng)被壓入棧中。因此,可以將該節(jié)點(diǎn)及其在棧中之前的所有節(jié)點(diǎn)彈出棧,這樣彈出的節(jié)點(diǎn)構(gòu)成的集合就是一個(gè)強(qiáng)連通分量。

        5) 繼續(xù)搜索,直到圖被遍歷完畢。Tarjan算法的時(shí)間復(fù)雜度為O(n+m),因?yàn)樵谠撍惴ㄖ?,每個(gè)節(jié)點(diǎn)僅被遍歷一次,每條邊也僅被遍歷一次。

        1.3 Tarjan 算法的競(jìng)賽意義

        各類程序設(shè)計(jì)競(jìng)賽里考察Tarjan的題目相比于其他算法題目并不是特別常見,但研究此類算法卻是小組成員學(xué)習(xí)其他圖論算法的必備條件之一。程序設(shè)計(jì)競(jìng)賽對(duì)計(jì)算機(jī)相關(guān)專業(yè)的學(xué)生來說有著很大的幫助,考驗(yàn)著學(xué)生的耐心、專注度、邏輯水平等。

        1.4 Tarjan 算法的C++代碼

        Tarjan算法的用C++實(shí)現(xiàn)的代碼如圖1所示。

        2 Tarjan 算法在程序設(shè)計(jì)競(jìng)賽中幾種典型運(yùn)用

        2.1 割點(diǎn)(割頂)問題[2]

        題目:給定一個(gè)包含n 個(gè)節(jié)點(diǎn)和m 條無向邊的圖,需要找出使圖不連通的最少節(jié)點(diǎn)集合,這個(gè)集合中的每個(gè)節(jié)點(diǎn)都是圖的割點(diǎn)。

        輸入:第一行輸入兩個(gè)正整數(shù)n,m。

        輸入m 條邊,每條邊用兩個(gè)正整數(shù)x 和y 表示,表示節(jié)點(diǎn)x 和節(jié)點(diǎn)y 之間有一條無向邊。輸出:第一行輸出割點(diǎn)個(gè)數(shù)。

        第二行按照節(jié)點(diǎn)編號(hào)從小到大輸出節(jié)點(diǎn),用空格隔開。

        樣例輸入:6 7

        1 2

        1 3

        1 4

        2 5

        3 5

        4 5

        5 6 樣例輸出:1

        5

        分析:標(biāo)準(zhǔn)Tarjan割點(diǎn)題,按照定義去求即可,用C++實(shí)現(xiàn)的代碼如圖2所示。

        2.2 The Cow Prom S 問題[3]

        題目:有一個(gè)n 個(gè)點(diǎn),m 條邊的有向圖,請(qǐng)求出這個(gè)圖點(diǎn)數(shù)大于1 的強(qiáng)聯(lián)通分量個(gè)數(shù)。

        輸入:第一行為兩個(gè)整數(shù)n 和m。

        從第二行到第m+1 行,每行給出兩個(gè)整數(shù)a 和b,表示有一條從節(jié)點(diǎn)a 指向節(jié)點(diǎn)b 的有向邊。

        輸出:僅一行,表示點(diǎn)數(shù)大于1 的強(qiáng)聯(lián)通分量個(gè)數(shù)。

        樣例輸入:5 4

        2 4

        3 5

        1 2

        4 1

        樣例輸出:1

        分析:要解決Tarjan 強(qiáng)連通分量問題,需要使用Tarjan 算法對(duì)圖進(jìn)行計(jì)算,并統(tǒng)計(jì)強(qiáng)連通分量的數(shù)量。其主要部分代碼如圖3所示。

        2.3 受歡迎的牛G 問題[4]

        題目:每頭奶牛都?jí)粝氤蔀榕E锢锏拿餍恰1凰心膛O矚g的奶牛就是一頭明星奶牛。每頭奶??偸窍矚g自己的,奶牛之間的“喜歡”是可以傳遞的——如果A 喜歡B,B 喜歡C,那么A 也喜歡C。牛欄里共有N 頭奶牛,給定一些奶牛之間的愛慕關(guān)系,請(qǐng)你算出有多少頭奶牛可以當(dāng)明星。

        輸入:第一行:兩個(gè)用空格分開的整數(shù):N 和M。

        接下來M 行:每行兩個(gè)用空格分開的整數(shù):A 和B,表示A 喜歡B。

        輸出:一行單獨(dú)一個(gè)整數(shù),表示明星奶牛的數(shù)量。

        樣例輸入:3 3

        1 2

        2 1

        2 3

        樣例輸出:1

        分析:利用Tarjan 算法對(duì)圖進(jìn)行強(qiáng)連通分量的計(jì)算并縮點(diǎn)后,可以得到一張有向無環(huán)圖(DAG),其中每個(gè)強(qiáng)連通分量被縮成一個(gè)點(diǎn)。在這個(gè)DAG 中,最受歡迎的奶??梢员欢x為出度為0的點(diǎn),也就是那些沒有任何后繼節(jié)點(diǎn)的點(diǎn)。這個(gè)強(qiáng)連通分量的奶牛數(shù)量極為最受歡迎的奶牛數(shù)量,同時(shí),如果有兩個(gè)及兩個(gè)以上的強(qiáng)連通分量則沒有最受歡迎的奶牛。因?yàn)檫@幾個(gè)強(qiáng)連通分量的奶牛無法相互傳遞“喜歡”,無法被所有奶牛喜歡。

        其主要代碼如圖4所示。

        2.4 縮點(diǎn)問題[5]

        題目:給定一個(gè)n 個(gè)點(diǎn)m 條邊有向圖,每個(gè)點(diǎn)有一個(gè)權(quán)值,求一條路徑,使路徑經(jīng)過的點(diǎn)權(quán)值之和最大。你只需要求出這個(gè)權(quán)值和。

        允許多次經(jīng)過一條邊或者一個(gè)點(diǎn),但是,重復(fù)經(jīng)過的點(diǎn),權(quán)值只計(jì)算一次。

        輸入:第一行兩個(gè)正整數(shù)n,m。

        第二行n 個(gè)整數(shù),其中第i 個(gè)數(shù)ai 表示點(diǎn)i 的點(diǎn)權(quán)。

        第三至m+2 行,每行兩個(gè)整數(shù)u,v,表示一條u→v 的有向邊。

        輸出:共一行,最大的點(diǎn)權(quán)之和。

        樣例輸入:2 2

        1 1

        1 2

        2 1 樣例輸出:2

        解析:由題意可知,需要找到一條點(diǎn)權(quán)和最大的路徑,且可以重復(fù)走。這樣第一時(shí)間就會(huì)考慮到出現(xiàn)環(huán)的情況,在題目要求權(quán)值最大的情況下,有環(huán)肯定需要把環(huán)上的點(diǎn)全走一遍。這時(shí)候就會(huì)用到縮點(diǎn)的技巧。如果不使用縮點(diǎn),很多算法都無法兼容。使用完縮點(diǎn)之后就可以正常處理。

        因?yàn)槭怯邢驁D,可以采用拓?fù)渑判?dp來進(jìn)行順推答案,維護(hù)到達(dá)點(diǎn)的最大權(quán)值和。其實(shí)現(xiàn)的主要部分代碼如圖5所示。

        2.5 Line Graph Matching(2021ICPC 沈陽(yáng)站)問題[6]

        題目:在圖論這門數(shù)學(xué)學(xué)科中,一個(gè)簡(jiǎn)單的無向加權(quán)圖G 的線圖是另一個(gè)簡(jiǎn)單的有向加權(quán)圖L(G)。線圖L(G)是一種由圖G 轉(zhuǎn)換而來的圖形,它的構(gòu)造方法是:將圖G 中的每個(gè)頂點(diǎn)用一條線段表示,線段的長(zhǎng)度等于該頂點(diǎn)的度數(shù);然后在L(G) 中,若圖G 中有兩條邊e1 和e2 共享一個(gè)頂點(diǎn)v,則在L(G) 中會(huì)用一個(gè)點(diǎn)來連接頂點(diǎn)e1 和頂點(diǎn)e2。因此,L(G) 表示的是圖G 中每?jī)蓷l邊之間的鄰接關(guān)系,這種關(guān)系可以通過連接L(G) 中的點(diǎn)來表示。

        具體來說,對(duì)于沒有環(huán)或多條邊的無向加權(quán)圖G,其線圖L(G)是一個(gè)無向的加權(quán)圖,滿足以下條件:

        L(G)的每個(gè)頂點(diǎn)表示G的一條邊;

        如果在圖G中,兩個(gè)頂點(diǎn)之間的邊的權(quán)重等于它們對(duì)應(yīng)邊的權(quán)重之和,并且這兩個(gè)頂點(diǎn)對(duì)應(yīng)的邊共享一個(gè)公共點(diǎn),那么這兩個(gè)頂點(diǎn)就是相鄰的。

        簡(jiǎn)單無向加權(quán)圖中的最大加權(quán)匹配被定義為一組邊,其中沒有兩條邊共享一個(gè)公共頂點(diǎn),并且該集合中的邊的權(quán)重之和被最大化。

        給定一個(gè)簡(jiǎn)單的無向加權(quán)連通圖G,你的任務(wù)是找到L(G)的最大加權(quán)匹配中的邊的權(quán)重之和。

        輸入:第一行包含兩個(gè)整數(shù)n和m,表示頂點(diǎn)數(shù)和給定圖G中的邊數(shù)。

        然后沿著m條線,其中第i條線包含三個(gè)整數(shù)u,u 和w,表明圖中的第i條邊是w的權(quán)重,并連接第u個(gè)頂點(diǎn)和第v個(gè)頂點(diǎn)。保證了圖G是連通的,并且不包含循環(huán)和多條邊。

        輸出:輸出包含單個(gè)整數(shù)的行,表示L(G)的最大加權(quán)匹配中的邊的權(quán)重之和。

        樣例輸入:5 6

        1 2 1

        1 3 2

        1 4 3

        4 3 4

        4 5 5

        2 5 6

        樣例輸出:21

        解析:該題有兩種情況,一種情況為邊的數(shù)量為偶數(shù),由深度優(yōu)先搜索樹可以推出,如果一個(gè)節(jié)點(diǎn)的子樹有一條邊未匹配,則使用父節(jié)點(diǎn)的邊進(jìn)行配對(duì),如果子樹完美配對(duì),則繼續(xù)往上遞歸。所以,偶數(shù)條邊一定可以把所有邊進(jìn)行完美配對(duì)。

        另一種情況為邊的數(shù)量為奇數(shù),可以按照上一種情況轉(zhuǎn)換,相當(dāng)于偶數(shù)條邊去掉了一條邊。

        刪邊之后會(huì)有兩種情況,一種為分成兩個(gè)聯(lián)通塊(刪的邊為割邊),另一種為偶數(shù)條邊的單個(gè)聯(lián)通塊(刪的邊為非割邊)。

        前者又分為兩個(gè)奇數(shù)條邊聯(lián)通塊,和兩個(gè)偶數(shù)條邊聯(lián)通塊。前者因?yàn)闀?huì)加大損耗,且可以轉(zhuǎn)換成另外兩種情況。

        最后結(jié)果為取兩種情況的最小值(刪掉損失最小的邊),剩下的即為最大的權(quán)重之和。其實(shí)現(xiàn)的主要部分代碼如圖6所示。

        3 Tarjan 算法在其他算法中的運(yùn)用

        拓?fù)渑判颍篢arjan算法可以用來對(duì)有向無環(huán)圖進(jìn)行拓?fù)渑判颉?/p>

        二分圖檢測(cè):Tarjan算法可以用于檢測(cè)一個(gè)無向圖是否為二分圖。

        最小生成樹:Tarjan算法可以用于Kruskal算法中的最小生成樹算法,以找到圖中的最小生成樹。

        有向無環(huán)圖的最長(zhǎng)路徑:通過對(duì)有向無環(huán)圖進(jìn)行拓?fù)渑判?,可以使用Tarjan算法來找到有向無環(huán)圖的最長(zhǎng)路徑。

        網(wǎng)絡(luò)流算法:Tarjan算法可以用于網(wǎng)絡(luò)流算法中,例如在最大流算法中,它可以用來找到殘量圖中的增廣路徑。

        總之,Tarjan算法是一個(gè)非常有用的算法,可以應(yīng)用于多種圖論的算法中,并且在實(shí)踐中得到廣泛的應(yīng)用。

        4 Tarjan 算法在工程上的運(yùn)用

        1) 編譯器中的語(yǔ)法分析:在編譯器中,Tarjan 算法被應(yīng)用于生成語(yǔ)法分析器。語(yǔ)法分析器的任務(wù)是將源代碼轉(zhuǎn)化為一個(gè)抽象語(yǔ)法樹,然后進(jìn)行語(yǔ)義分析和生成代碼。Tarjan算法可以在語(yǔ)法分析器中用于檢測(cè)循環(huán)依賴和死鎖等問題。

        2) 數(shù)據(jù)庫(kù)中的事務(wù)管理:在數(shù)據(jù)庫(kù)管理系統(tǒng)中,Tarjan算法可以用于事務(wù)管理,特別是在分布式數(shù)據(jù)庫(kù)中。在這種情況下,Tarjan算法可以用于檢測(cè)數(shù)據(jù)庫(kù)中的死鎖,以確保事務(wù)的正確執(zhí)行。

        3) 圖形編輯器中的拓?fù)渑判颍涸趫D形編輯器中,Tarjan算法可以用于執(zhí)行拓?fù)渑判颍员阍谔幚碛邢驘o環(huán)圖時(shí)能夠按照正確的順序處理圖形元素。

        4) 軟件工程中的模塊依賴分析:在軟件工程中,Tarjan算法可以用于模塊依賴分析。模塊依賴分析可以幫助開發(fā)人員識(shí)別軟件模塊之間的依賴關(guān)系,以便更好地組織和管理代碼庫(kù)。

        5) 網(wǎng)絡(luò)協(xié)議中的路由算法:在網(wǎng)絡(luò)協(xié)議中,Tarjan 算法可以用于路由算法,以幫助網(wǎng)絡(luò)節(jié)點(diǎn)找到最佳的路由路徑。例如,在因特網(wǎng)中,Tarjan算法可以用于實(shí)現(xiàn)BGP(Border Gateway Protocol) 協(xié)議,以幫助互聯(lián)網(wǎng)服務(wù)提供商找到最佳的路由路徑。

        總的來說,Tarjan算法是一種非常通用的算法,可以應(yīng)用于多個(gè)領(lǐng)域和場(chǎng)景中。

        5 總結(jié)

        Tarjan算法在解決強(qiáng)連通分量問題方面具有重要的地位,它在解決強(qiáng)連通分量問題方面具有重要的地位,還可以應(yīng)用到許多其他的圖算法中。它不僅在理論上有著優(yōu)秀的性能表現(xiàn),而且在實(shí)際應(yīng)用中也得到了廣泛的使用和驗(yàn)證。

        猜你喜歡
        實(shí)例
        應(yīng)用GGB研究一類不等式求解實(shí)例及拓展
        信用證償付實(shí)例剖析
        就地瀝青熱再生應(yīng)用實(shí)例探討
        Catalan數(shù)及幾種應(yīng)用實(shí)例
        商情(2017年42期)2017-12-26 12:34:41
        一起肉鴨球蟲病的診治實(shí)例
        完形填空Ⅱ
        完形填空Ⅰ
        國(guó)外先進(jìn)信息技術(shù)應(yīng)用實(shí)例
        杭州科技(2014年4期)2014-02-27 15:26:58
        基于實(shí)例的純電動(dòng)汽車動(dòng)力系統(tǒng)匹配與驗(yàn)證
        河南科技(2014年1期)2014-02-27 14:04:25
        理想化最速下降法及其逼近實(shí)例
        青青草成人在线免费视频| 亚洲av无码专区在线亚| 久久狠狠爱亚洲综合影院| av免费网站免费久久网| 欧洲多毛裸体xxxxx| 国产色综合天天综合网| 亚洲综合色婷婷久久| 久久久黄色大片免费看| 隔壁老王国产在线精品| 国产乱人伦av在线无码| 国产高清白浆| 丝袜av乱码字幕三级人妻| 国产精品无码一区二区在线观一| 国产精品视频一区二区三区四 | 国产高清在线精品一区αpp| 成人性生交大片免费看激情玛丽莎| 亚洲国产精品无码成人片久久| 性生交大全免费看| 妺妺窝人体色www聚色窝韩国| 美女被躁到高潮嗷嗷免费观看| 精人妻无码一区二区三区| a亚洲va欧美va国产综合| 免费va国产高清不卡大片| 国产成人精品久久二区二区91 | 亚洲av色先锋资源电影网站| 亚洲在战AV极品无码| 久久免费亚洲免费视频| 少妇内射兰兰久久| 四虎精品成人免费观看| 国产精品不卡免费版在线观看| 日韩日韩日韩日韩日韩日韩日韩| 欧美gv在线观看| 午夜无码无遮挡在线视频| 一本色道久久88加勒比| 久久久久久国产精品免费免费| 少妇AV射精精品蜜桃专区| 骚货人妻视频中文字幕| 狠狠色丁香婷婷综合潮喷| 国产无遮挡a片又黄又爽| 男女上床视频免费网站| 日韩人妖视频一区二区|