青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

POJ 3352 Road Construction 雙連通分量+縮點

Description

It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

Sample Input

Sample Input 1
10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10
Sample Input 2
3 3
1 2
2 3
1 3

Sample Output

Output for Sample Input 1
2
Output for Sample Input 2
0

Source


   

    題目大意:給定一個雙向連通的公路網,當某些公路路段檢修的時候可能會由于該段公路不通,可能會使某些旅游點之間無法通行,求至少新建多少條公路,使得任意對一段公路進行檢修的時候,所有的旅游景點之間仍然暢通;

    分析:檢修某一路段導致公路網不暢通的原因必然是該段公路在圖中是橋(割邊),因此完全暢通的方法就是,加最若干條邊,使圖中不存在橋。先找出圖中所有的雙連通分量,將雙連通分量進行縮點,得到一個樹形圖,求出這個樹形圖中度為1的點的個數,新加邊的條數即是(度為1的點數目+1)/2,考慮到題目只要求求度為1的點數目,因此可以部分縮點,利用并查集,保存每個割邊的頂點,統計每個頂點在并查集中的代表元的度數即可。
    Sample 1中存在4個雙連通分量:{1},{2,5,6},{3,7,8},{4,9,10},進行縮點之后,求得一個4個節點的樹形圖,其中一個點的度數為3,其余3個點的度數為1,得到需要加的邊的數目為(3+1)/2=2。

#include <iostream>
#include 
<vector>
using namespace std;

const int MAXN = 5001;
vector
< vector<int> > adj;
int cnt,low[MAXN],pre[MAXN],visit[MAXN],degree[MAXN];

void dfs(int u,int v){
    visit[u]
=1;
    pre[u]
=cnt++,low[u]=pre[u];
    
int i,len=adj[u].size();
    
for(i=0;i<len;i++){
        
if(adj[u][i]==v) continue;
        
if(!visit[adj[u][i]]) dfs(adj[u][i],u);
        
if(low[adj[u][i]]<low[u]) low[u]=low[adj[u][i]];
    }

    visit[u]
=2;
}

int main(){
    
int i,j,u,v,n,m,len,ans;
    scanf(
"%d %d",&n,&m);
    adj.assign(n
+1,vector<int>());
    
while(m--){
        scanf(
"%d %d",&u,&v);
        adj[u].push_back(v),adj[v].push_back(u);
    }

    memset(visit,
0,sizeof(visit));
    cnt
=0,dfs(1,1);
    memset(degree,
0,sizeof(degree));
    
for(i=1;i<=n;i++){
        len
=adj[i].size();
        
for(j=0;j<len;j++)
            
if(low[i]!=low[adj[i][j]])
                degree[low[i]]
++;
    }

    
for(ans=i=0;i<=n;i++)
        
if(degree[i]==1) ans++;
    printf(
"%d\n",(ans+1)/2);
    
return 0;
}

posted on 2009-05-29 18:53 極限定律 閱讀(1587) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC

評論

# re: POJ 3352 Road Construction 雙連通分量+縮點 2009-08-03 10:47 路人

11 14
1 2
1 3
1 4
2 5
6 11
2 6
5 6
5 11
3 7
3 8
7 8
4 9
4 10
9 10

你的程序,這組數據時錯誤的。。  回復  更多評論   

# re: POJ 3352 Road Construction 雙連通分量+縮點 2009-08-04 09:46 mythit

@路人
多謝指正  回復  更多評論   

# re: POJ 3352 Road Construction 雙連通分量+縮點 2011-07-25 19:14 過客

void dfs(int u,int v){
visit[u]=1;
pre[u]=cnt++,low[u]=pre[u];
int i,len=adj[u].size();
for(i=0;i<len;i++){
if(adj[u][i]==v) continue;
if(!visit[adj[u][i]]) dfs(adj[u][i],u);
if(low[adj[u][i]]<low[u]) low[u]=low[adj[u][i]];
}
visit[u]=2;
}
最后一句 visit[u]=2;有什么用啊,求解釋  回復  更多評論   

<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲综合二区| 国产精品日韩欧美大师| 一区二区三区www| 裸体一区二区| 日韩亚洲精品在线| 欧美国产免费| 激情小说另类小说亚洲欧美| 午夜国产一区| 久久成人在线| 久久另类ts人妖一区二区| 国产视频一区在线| 性欧美长视频| 久久亚洲一区二区| 亚洲精品一线二线三线无人区| 久久精品二区三区| 麻豆精品视频| 亚洲精品免费看| 亚洲一级特黄| 激情国产一区二区| 亚洲人久久久| 蜜臀av国产精品久久久久| 亚洲乱码一区二区| 99精品欧美一区二区三区综合在线| 欧美精品在线免费观看| 亚洲三级电影在线观看| 亚洲午夜伦理| 国产精品99久久99久久久二8| 一区二区三区产品免费精品久久75| 国产精品亚洲а∨天堂免在线| 久久在线免费观看视频| 亚洲男人的天堂在线观看 | 欧美亚洲日本网站| 新狼窝色av性久久久久久| 在线看欧美日韩| 日韩视频一区二区三区| 亚洲欧美另类在线观看| 欧美一区二区视频免费观看| 国产麻豆午夜三级精品| 国产精品午夜春色av| 国产一区二区观看| 亚洲人成免费| 99视频精品全国免费| 国产欧美日韩精品丝袜高跟鞋| 伊人久久噜噜噜躁狠狠躁| 亚洲高清不卡一区| 国产欧美精品日韩| 国产精品久久久久免费a∨大胸| 国产精品一区二区三区久久久 | 欧美激情亚洲自拍| 久久久久国产一区二区三区四区| 欧美激情第9页| 久久精品国产一区二区三区| 欧美日韩成人网| 亚洲国产三级在线| 影音先锋日韩精品| 亚洲专区在线| 免费一级欧美片在线播放| 欧美国产日韩一区| 久久午夜精品一区二区| 欧美国产激情二区三区| 国产区精品视频| 一区二区三区**美女毛片| 亚洲精品久久7777| 欧美激情一区二区三区| 欧美激情精品久久久六区热门 | 一本一道久久综合狠狠老精东影业 | 亚洲视频综合| 9色国产精品| 欧美激情中文字幕乱码免费| 亚洲成色777777女色窝| 亚洲国产欧美久久| 久久一区二区三区av| 国产精品试看| 亚洲欧美激情四射在线日| 亚洲一区二区三区免费观看 | 国产欧美日韩三区| 在线亚洲自拍| 午夜天堂精品久久久久 | 91久久久久| 欧美韩日精品| 欧美成人资源| 在线综合亚洲| 亚洲深夜福利网站| 西瓜成人精品人成网站| 国产美女精品| 久久综合影音| 91久久久在线| 亚洲免费网站| 一区二区在线观看视频在线观看| 亚洲一区二区在线观看视频| 欧美午夜精品久久久久久久| 亚洲精品日韩精品| 亚洲午夜成aⅴ人片| 国产丝袜美腿一区二区三区| 中文网丁香综合网| 国产精品video| 欧美一区二区三区视频免费播放 | 在线观看av一区| 欧美精品偷拍| 亚洲一区中文字幕在线观看| 免费观看成人| 亚洲影院在线| 亚洲黄色高清| 国产精品美女久久久久久久| 久久精品国产免费看久久精品| 9久草视频在线视频精品| 久久精品视频免费播放| 亚洲精品免费在线播放| 91久久午夜| 欧美日韩免费一区| 久久久久九九九| 一本到高清视频免费精品| 免费高清在线视频一区·| 亚洲欧美日韩国产综合| 亚洲国产精品t66y| 国产一区二区电影在线观看 | 亚洲国产高潮在线观看| 欧美午夜精品一区| 欧美成人一区二区三区| 亚洲国产精品传媒在线观看| 欧美一区二区三区免费观看视频| 欧美福利影院| 久久狠狠婷婷| 亚洲综合色自拍一区| 91久久在线观看| 男女视频一区二区| 久久精彩免费视频| 亚洲欧美视频在线观看视频| 日韩一二三区视频| 亚洲精品1区2区| 久久一区视频| 亚洲综合国产| 久久精品导航| 亚洲一区美女视频在线观看免费| 欧美精品国产精品| 美女主播视频一区| 久久蜜桃香蕉精品一区二区三区| 久久九九国产精品| 欧美在线啊v一区| 亚洲欧美久久久| 一区二区三区免费网站| 尤物精品在线| 亚洲丰满少妇videoshd| 精品动漫一区二区| 国产精品久久久久久超碰| 欧美激情1区2区| 免费在线观看精品| 六月婷婷久久| 久久另类ts人妖一区二区| 激情校园亚洲| 一区二区在线观看视频| 在线电影欧美日韩一区二区私密| 欧美专区在线| 亚洲欧美另类在线| 久久狠狠一本精品综合网| 久久精品123| 久久人人97超碰国产公开结果| 欧美不卡高清| 欧美国产日本在线| 亚洲日本久久| 一区二区三区欧美| 亚洲欧美综合v| 久久久精品久久久久| 久久综合给合| 欧美日韩美女在线观看| 欧美性猛交xxxx免费看久久久| 久久成人亚洲| 蜜桃av一区二区三区| 欧美日韩在线一区二区三区| 欧美日韩亚洲另类| 国产精品爽黄69| 韩国福利一区| 亚洲人www| 老司机精品视频一区二区三区| 你懂的成人av| 亚洲精品国产精品国自产观看| 亚洲精选大片| 亚洲一区二区动漫| 久久天堂av综合合色| 亚洲国产高清在线| 午夜影院日韩| 久久免费黄色| 99精品国产一区二区青青牛奶| 可以看av的网站久久看| 亚洲国产精品嫩草影院| 久久久一区二区| 亚洲高清二区| 亚洲网站在线| 免费国产自线拍一欧美视频| 欧美午夜无遮挡| 在线日韩中文字幕| 亚洲天堂av图片| 亚洲精品视频在线观看网站| 亚洲一级黄色片| 男女精品视频| 亚洲免费在线视频一区 二区| 欧美黄色一级视频| 亚洲欧美日韩国产另类专区| 久久久噜噜噜久久中文字免| 欧美日韩人人澡狠狠躁视频|