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

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>
            一本色道久久综合亚洲精品不卡 | 欧美电影免费网站| 在线看国产日韩| 欧美国产日韩精品| 欧美成人国产va精品日本一级| 亚洲欧洲日产国产网站| 亚洲美女少妇无套啪啪呻吟| 国产精品久久久久久久久久久久 | 亚洲高清视频在线观看| 亚洲国产精品久久久久婷婷884| 久久久久国产成人精品亚洲午夜| 亚洲国产高潮在线观看| 亚洲免费观看视频| 国产欧美欧美| 亚洲国产岛国毛片在线| 国产精品久久久久久久久久三级| 久久9热精品视频| 美女视频一区免费观看| 亚洲午夜精品久久| 久久国内精品自在自线400部| 最新精品在线| 午夜精品在线| 日韩亚洲欧美在线观看| 午夜综合激情| 一区二区动漫| 久热精品视频在线| 性视频1819p久久| 欧美sm视频| 久久国产精品一区二区三区| 欧美高清在线观看| 久久久久久九九九九| 欧美/亚洲一区| 久久久精品性| 国产精品扒开腿做爽爽爽视频| 美女久久网站| 国产欧美日韩中文字幕在线| 亚洲欧洲精品一区二区精品久久久 | 老司机午夜精品视频| 欧美美女bbbb| 欧美国产大片| 国产一区二区三区在线观看免费视频 | 91久久久国产精品| 国内精品免费在线观看| 亚洲午夜激情免费视频| 亚洲欧洲精品天堂一级| 久久精品在线播放| 先锋影音一区二区三区| 欧美人成在线| 亚洲激情第一区| 最新成人av网站| 老司机免费视频久久| 久久久久久精| 国内成人精品2018免费看| 亚洲在线观看| 亚洲欧美日韩国产成人| 欧美午夜精品电影| 日韩视频中文字幕| 日韩亚洲国产欧美| 欧美久久99| 99视频一区| 亚洲在线1234| 国产精品毛片va一区二区三区| 一本久道久久久| 亚洲与欧洲av电影| 国产拍揄自揄精品视频麻豆| 亚洲欧美日本国产有色| 午夜欧美大尺度福利影院在线看| 欧美特黄一区| 午夜精品美女自拍福到在线| 羞羞色国产精品| 国产一本一道久久香蕉| 久久久91精品国产| 久久综合网hezyo| 亚洲激情一区二区| 欧美国产日韩亚洲一区| 亚洲九九精品| 欧美一区二区在线看| 国产一区自拍视频| 久久中文字幕一区| 亚洲欧洲另类国产综合| 亚洲一区二区三区涩| 国产精品手机视频| 久久久国产一区二区三区| 欧美国产成人在线| 亚洲无吗在线| 激情综合久久| 欧美日本高清视频| 亚洲欧美日韩精品一区二区| 老司机免费视频一区二区| 日韩视频在线观看国产| 国产精品青草久久| 美女国内精品自产拍在线播放| 亚洲精品视频在线观看免费| 欧美在线播放| 亚洲免费激情| 国产日韩综合一区二区性色av| 久久综合99re88久久爱| 在线视频欧美一区| 欧美成人激情视频| 欧美亚洲一区| 亚洲精品资源| 国产主播一区二区| 欧美人与禽猛交乱配视频| 亚洲一区二区三区四区五区午夜 | 久久综合影视| 亚洲伊人色欲综合网| 亚洲第一久久影院| 欧美在线视频全部完| 99天天综合性| 亚洲第一成人在线| 国产精品亚洲а∨天堂免在线| 蜜臀av一级做a爰片久久 | 91久久精品一区| 免费成人激情视频| 久久av一区| 亚洲综合欧美日韩| 日韩午夜中文字幕| 在线日韩中文| 黄色亚洲精品| 国产精品永久免费观看| 欧美日韩蜜桃| 欧美破处大片在线视频| 久久久夜色精品亚洲| 欧美亚洲视频| 亚洲免费在线观看| 亚洲一区二区三区精品动漫| 亚洲精品五月天| 91久久精品一区二区三区| 欧美福利一区二区三区| 另类综合日韩欧美亚洲| 久久久久一区二区三区四区| 欧美一区91| 欧美在线观看www| 亚洲欧美中文日韩v在线观看| 中文高清一区| 中日韩在线视频| 中文成人激情娱乐网| 亚洲神马久久| 亚洲影院在线观看| 亚洲欧美日韩爽爽影院| 午夜国产精品视频| 亚洲欧美中文日韩v在线观看| 亚洲欧美日韩一区二区在线| 亚洲欧美成人| 久久精品动漫| 免费久久99精品国产自在现线| 久久夜色精品亚洲噜噜国产mv| 久久亚洲精品一区| 欧美夫妇交换俱乐部在线观看| 欧美国产日本| 日韩视频免费| 亚洲欧美日韩精品久久奇米色影视| 亚洲综合首页| 久久久999国产| 欧美激情一区二区三区四区| 欧美日韩国产黄| 国产精品私人影院| 激情综合网址| 在线视频亚洲| 久久久久久欧美| 欧美激情中文字幕乱码免费| 亚洲精品欧美一区二区三区| 亚洲视频在线一区| 久久久久国产精品一区| 模特精品在线| 国产精品推荐精品| 尤物在线精品| 亚洲一二三级电影| 久久这里有精品视频| 亚洲国产精品精华液2区45| 一区二区久久久久久| 欧美怡红院视频| 欧美另类69精品久久久久9999| 国产精品久久久久久久久免费桃花| 国内欧美视频一区二区| 亚洲美女精品久久| 久久美女性网| 亚洲免费av观看| 久久精品卡一| 国产精品毛片一区二区三区| 伊人久久亚洲美女图片| 亚洲一二三区精品| 欧美激情久久久久| 亚洲欧美亚洲| 欧美午夜精品久久久| 一区二区在线视频播放| 亚洲欧美日韩精品一区二区 | 欧美激情在线播放| 欧美一级夜夜爽| 国产精品久久久一区麻豆最新章节 | 在线日韩欧美视频| 欧美在线黄色| 99re6这里只有精品| 久久免费高清| 国产一区二区三区在线观看免费视频 | 欧美电影美腿模特1979在线看| 亚洲午夜精品| 欧美日韩午夜在线| 最新成人av在线| 欧美黑人国产人伦爽爽爽|