• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            bon

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            強聯通分量:是指點的一個子集以及這些點附帶的邊,這個子集中任意兩點能互相到達對方。


            算法描述:

            1. 用dfs遍歷有向圖,形成一個森林(注意是森林),遍歷時記下每個節點 i 所有子孫訪問完成的時刻。如 i 有子孫a,b,c,則dfs(a), dfs(b), dfs(c)后將時間戳賦給 finish[i]。

            2. 將所有邊反向,構成新的圖GT

            3. 在GT上按點的時間戳降序做dfs,生成一個森林,每棵樹就是一個強聯通分量了。


            強聯通分量的性質:

            1. 若 u,v 處于同一強聯通分量中,則所有邊反向后,它們任處在同一強聯通分量中。

            2. 在第二次 dfs 中,設點 u 的時間戳是當前所有未訪問的點中最大的,則 u 所在的強聯通分量 C 沒有邊指向其它未訪問的強聯通分量C'(注意是在GT中)。因為若存在這樣的邊,則在G中存在邊從 C' 的點指向 C,則C‘中點時間戳肯定比 u 大(回想一下第一次 dfs 時我們是怎樣對點標時間戳的),與假設矛盾。

            下面是代碼,最后是測試文件。輸出每個點屬于哪個強聯通分量。

            #include <iostream>
            #include 
            <list>
            #include 
            <algorithm>

            using namespace std;

            const int maxn=100;

            // 用于第一次dfs時記錄每個點的finish時間戳
            struct finish{
                
            int id;
                
            int ftime;
            }f[maxn];

            // 這個結構體用于第二次dfs時記錄每個點屬于哪個塊
            struct component{
                
            int cid;
                
            int id;
            }comp[maxn];

            // 排序用
            bool operator <(const finish &a, const finish &b)
            {
                
            return a.ftime<b.ftime;
            }
            // 鄰接表存儲
            list<int> l[maxn];
            list
            <int> lr[maxn];

            // dfs訪問標識數組
            int visit[maxn];

            int t;
            int n,e;

            void dfs1(int k,int id)
            {
                visit[k]
            =id;
                
            for(list<int>::iterator it=l[k].begin();it!=l[k].end();it++){
                    
            int x=(int)(*it);
                    
            if(visit[x]==-1) dfs1(x,id);
                }
                f[k].ftime
            =++t;
                f[k].id
            =k;
            }

            void dfs2(int k,int cid)
            {
                visit[k]
            =cid;
                comp[k].id
            =k;
                comp[k].cid
            =cid;
                
            for(list<int>::iterator it=lr[k].begin();it!=lr[k].end();it++){
                    
            int x=(int)(*it);
                    
            if(visit[x]==-1) dfs2(x,cid);
                }
            }

            // 將圖的邊反向
            void reverse()
            {
                
            for(int i=0;i<n;i++){
                    
            for(list<int>::iterator it=l[i].begin();it!=l[i].end();it++){
                        lr[(
            int)(*it)].push_back(i);
                    }
                }
            }

            void clearList()
            {
                
            int i;
                
            for(i=0;i<n;i++) l[i].clear(),lr[i].clear();
            }

            bool read()
            {
                
            int i,j,k;
                
            if(scanf("%d%d",&n,&e)==EOF) return false;
                
            for(i=0;i<e;i++){
                    scanf(
            "%d%d",&j,&k);
                    l[j
            -1].push_back(k-1);
                }
                
            return true;
            }

            void solve()
            {
                
            int i,j,k;
                memset(visit,
            -1,sizeof(visit));
                

                
            // 第一次dfs記錄時間戳
                int id=1;
                t
            =0;
                
            for(i=0;i<n;i++if(visit[i]==-1){        
                    dfs1(i,id
            ++);
                }
                
            //for(i=0;i<n;i++) printf("%d ",visit[i]);
                
            //printf("\n");

                
            // 根據finish的時間戳來排序
                sort(f,f+n);

                
            // 所有邊反向
                reverse();

                
            for(i=n-1;i>=0;i--) printf("%d ",f[i].id);
                printf(
            "\n");
                memset(visit,
            -1,sizeof(visit));
                
            int cid=1;
                
            for(i=n-1;i>=0;i--){
                    
            int x=f[i].id;
                    
            if(visit[x]==-1) dfs2(x,cid++);
                }
                
            for(i=0;i<n;i++) printf("%d ",comp[i].cid);
            }

            int main()
            {
                freopen(
            "graph.txt","r",stdin);
                
            while(read()){
                    solve();
                    clearList();
                }
            }

            // 測試文件,包括兩個圖,第一個是聯通的,第二個不聯通
            8 14
            1 3
            2 1
            3 2
            3 4
            2 4
            3 6
            4 5
            5 4
            6 5
            6 7
            7 6
            5 8
            7 8
            8 8
            4 4
            1 2
            2 1
            3 4
            4 3

            posted on 2008-03-28 12:16 bon 閱讀(995) 評論(0)  編輯 收藏 引用 所屬分類: Notes on Introduction to Algorithms
            Google PageRank 
Checker - Page Rank Calculator
            99久久做夜夜爱天天做精品| 久久er国产精品免费观看2| 久久精品国产精品亚洲人人| 国产午夜福利精品久久| 国产亚洲美女精品久久久 | 亚洲国产精品无码成人片久久| 色偷偷久久一区二区三区| AAA级久久久精品无码片| 色婷婷狠狠久久综合五月| 99久久免费国产精品特黄| 色综合久久久久综合体桃花网| 国内精品伊人久久久久AV影院| 久久久久国产视频电影| 久久棈精品久久久久久噜噜| 久久性精品| 久久综合丝袜日本网| 久久久久久久久久久久久久 | 久久精品国产亚洲av麻豆蜜芽 | 久久久精品人妻一区二区三区四| 国产成人精品久久一区二区三区av| 欧美一级久久久久久久大片| 精品国产VA久久久久久久冰| 天天综合久久一二三区| 国产精品久久国产精品99盘| 欧美午夜精品久久久久久浪潮| 亚洲狠狠婷婷综合久久久久 | 久久国产免费观看精品3| A级毛片无码久久精品免费| 久久婷婷人人澡人人| 爱做久久久久久| 91久久国产视频| 日本道色综合久久影院| 久久综合中文字幕| 亚洲国产二区三区久久| 久久综合亚洲欧美成人| 亚洲色欲久久久综合网东京热| 欧美色综合久久久久久| 欧美日韩中文字幕久久伊人| 久久国产精品久久国产精品| 国内精品久久九九国产精品| 久久久老熟女一区二区三区|