• <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>

            pku 3177 Redundant Paths 無向圖找橋、縮點問題

            題意很簡單,一個無向圖,要求在圖中添加最少的邊,使得任意兩節點間均有2條或以上不同的路徑。
            這題本質上看是添邊然后構成一個強聯通圖。
            算法是這樣,首先找到橋,將強聯通分支縮點,這樣構成一棵樹。要把樹變為強聯通圖,即將葉節點兩兩配對即可(如果有奇數個頁節點,則將未配對節點再添加一條邊即可)。
            注意!無向圖找橋的時候要對邊加以標記,除非沒有平行邊,否則不要在DFS中用父節點防止走2環
             1 # include <stdio.h>
             2 # include <string.h>
             3 # include <stdbool.h>
             4 # define MAX 0xfffffff
             5 # define min(a,b) ((a)<(b)?(a):(b))
             6 int n,m;
             7 int g[5001],v[20001],nxt[20001],c=0;
             8 int cnt=0,low[5001],cid[5001],cnum=0;
             9 bool map[5001][5001];
            10 bool used[20001];
            11 int stack[5001],top=-1;
            12 void dfs(int pos)
            13 {
            14      int p,now=cnt++;
            15      stack[++top]=pos;
            16      low[pos]=now;
            17      for(p=g[pos];p!=-1;p=nxt[p])
            18      if(!used[p>>1])
            19      {
            20        used[p>>1]=1;
            21        if(low[v[p]]==-1)
            22          dfs(v[p]);
            23         low[pos]=min(low[pos],low[v[p]]);
            24        if(low[v[p]]>now)
            25        {
            26           do
            27           {
            28               cid[stack[top]]=cnum;
            29           }while(stack[top--]!=v[p]);
            30           cnum++;
            31        }
            32      }
            33 }
            34 
            35 int main()
            36 {
            37    // freopen("input.txt","r",stdin);
            38    // freopen("output.txt","w",stdout);
            39     int i,p,ans=0;
            40     scanf("%d%d",&n,&m);
            41     memset(g,-1,sizeof(g));
            42     while(m--)
            43     {
            44        int s,t;
            45        scanf("%d%d",&s,&t);
            46        v[c]=t;
            47        nxt[c]=g[s];
            48        g[s]=c++;
            49        v[c]=s;
            50        nxt[c]=g[t];
            51        g[t]=c++;
            52        
            53     }    
            54     memset(low,-1,sizeof(low));
            55     memset(used,0,sizeof(used));
            56     dfs(1);
            57     while(top>=0)
            58        cid[stack[top--]]=cnum;
            59     cnum++;
            60     memset(map,0,sizeof(map));
            61     for(i=1;i<=n;i++)
            62       for(p=g[i];p!=-1;p=nxt[p])
            63       {
            64           if(cid[v[p]]!=cid[i])
            65              map[cid[i]][cid[v[p]]]=map[cid[v[p]]][cid[i]]=1;
            66       }
            67     for(i=0;i<cnum;i++)
            68     {
            69       int cal=0;
            70       for(p=0;p<cnum;p++)
            71          cal+=map[p][i];
            72       ans+=(cal==1?1:0);
            73     }
            74     printf("%d\n",(ans+1)>>1);
            75   //  system("pause");
            76     return 0;
            77 }
            78 


            posted on 2010-10-25 23:39 yzhw 閱讀(665) 評論(0)  編輯 收藏 引用 所屬分類: graph

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国内精品久久久久久久亚洲| 国产精品熟女福利久久AV| 狠狠久久综合伊人不卡| 久久亚洲欧洲国产综合| 精品国产乱码久久久久久人妻| 久久久婷婷五月亚洲97号色| 大蕉久久伊人中文字幕| 久久99热这里只有精品国产| 久久国产福利免费| 男女久久久国产一区二区三区| 91久久精品国产91性色也| 2019久久久高清456| 狠狠色伊人久久精品综合网| 久久亚洲国产成人精品性色| 精品水蜜桃久久久久久久| 久久久久亚洲Av无码专| 99久久免费国产精品特黄| 色综合久久综精品| 国产精品久久久亚洲| 狠狠综合久久综合88亚洲| 久久久久国产亚洲AV麻豆| 久久电影网一区| 久久夜色精品国产噜噜亚洲AV| 久久午夜无码鲁丝片午夜精品| 国产成年无码久久久久毛片| 超级碰碰碰碰97久久久久| 久久亚洲高清综合| 久久久WWW成人免费毛片| 国产精品一区二区久久精品无码 | 久久久久久久尹人综合网亚洲| 日韩精品久久久久久久电影| 欧美色综合久久久久久| 久久精品免费大片国产大片| 久久免费视频6| 久久青青国产| 91麻豆国产精品91久久久| 久久经典免费视频| 亚洲va久久久噜噜噜久久男同| 久久久久久国产精品无码下载| 亚洲中文字幕无码久久2017| 久久久久久久人妻无码中文字幕爆 |