POJ 3352 도로 건설 (변 쌍 연통 분량)

POJ 3352 도로 건설 (변 쌍 연통 분량)
http://poj.org/problem?id=3352
제목:
        연 결 된 무방 향 그림 을 드 리 겠 습 니 다. 이 그림 에 최소한 몇 개의 변 을 추가 하면 이 그림 을 이중 연결 그림 으로 만 들 수 있 습 니까?
분석:
        문제 풀이 방향 은 다음 블 로 그 를 참고 하 세 요.
http://blog.csdn.net/lyy289065406/article/details/6762370
        우선 이 그림 자체 가 하나의 사 이 드 더 블 연결 그림 이 라면 우 리 는 사 이 드 를 추가 할 필요 가 없습니다. 그래서 우 리 는 먼저 이 무방 향 그림 에 대해 tarjan () 함수 로 그림 의 모든 다 리 를 구 해 야 합 니 다.
        모든 다리 에 있어 서 그것 은 두 개의 서로 다른 변 의 쌍 연결 분량 을 연결 하고 있다. (한 점 이 있 더 라 도 한 변 의 쌍 연결 분량 이 라 고 할 수 있다) 같은 변 의 쌍 연결 분량 에 대해 우 리 는 다음 과 같은 결론 을 내 렸 다. low [i] 값 이 같은 점 은 반드시 같은 변 의 쌍 연결 분량 에 속한다.
        그리고 우리 가 만약 에 한 변 을 추가 하려 면 우 리 는 반드시 서로 다른 변 의 쌍 연결 분량 에 속 하 는 두 점 사이 에 추가 해 야 한다. 우 리 는 같은 변 의 쌍 연결 분량 에 변 을 넣 으 면 아무런 의미 가 없다. 그래서 우 리 는 모든 다 리 를 구 한 후의 그림 을 간소화 한다. 우 리 는 각 변 의 쌍 연결 분량 을 하나의 수축 점 을 본 다음 에 모든 다리 로 모든 수축 점 (즉, 각 변 의 쌍 연결 분량) 을 연결한다.. 다음 과 같은 예 에서 보 듯 이:

그래서 우 리 는 G 그림 의 축 점 트 리 에 사 이 드 를 추가 하여 하나의 사 이 드 더 블 연결 그림 으로 만 들 면 됩 니 다. 이렇게 하면 우 리 는 우리 가 추가 한 사 이 드 가 가장 적 고 마지막 그림 이 전체 사 이 드 더 블 연결 이라는 것 을 보증 할 수 있 습 니 다.
        그러면 우 리 는 나무 한 그루 에 몇 개의 변 을 추가 해 야 그것 을 두 개의 연결 로 만 들 수 있 습 니까?
        다음 과 같은 결론 이 있다. 한 그루 의 무방 향 나무 에 대해 우 리 는 그것 을 변 쌍 연통 도로 바 꾸 려 면 첨가 해 야 할 변수 = = (나무의 도수 가 1 인 점 의 개수 + 1) / 2
(이상 결론 은 증명 하기 어렵다)
AC 코드:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
int n,m;
vector<int> G[maxn];
int dfs_clock;
int pre[maxn],low[maxn];
int degree[maxn];
int tarjan(int u,int fa)
{
    int lowu=pre[u]=++dfs_clock;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa) continue;
        if(!pre[v])
        {
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
        }
        else if(pre[v]<pre[u])
            lowu=min(lowu,pre[v]);
    }
    return low[u]=lowu;
}
int main()
{
    scanf("%d%d",&n,&m);
    dfs_clock=0;
    memset(pre,0,sizeof(pre));
    memset(degree,0,sizeof(degree));
    for(int i=1;i<=n;i++) G[i].clear();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    tarjan(1,-1);//       low ,     low           
    for(int u=1;u<=n;u++)//     
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(low[u]!=low[v]) degree[low[v]]++;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)if(degree[i]==1)
        cnt++;
    printf("%d
",(cnt+1)/2 );
}