poj 3177 Redundant Paths (双联通）

/*******************************************************
题目：Redundant Paths (poj 2177)
链接：http://poj.org/problem?id=3177
算法：双联通+缩点
思路：先找出所有双联通分量，把这些分量缩成一个点
       再找出所有度为一的点，用这些点数加一除2就可以了


********************************************************/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#include<stack>
using namespace std;

const int mx=5005;
vector<int>g[mx];
stack<int>s;
int dfn[mx],low[mx];
int bcc[mx],vs[mx];
int in[mx];
int dfs_cut,bcc_cut;

void dfs(int u,int fa)
{
    dfn[u]=low[u]=++dfs_cut;
    vs[u]=1;
    s.push(u);
    int p=1;    ///去重
    for (int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if (v==fa&&p)
        {
            p=0;
            continue;
        }
        if (!vs[v])
        {
            dfs(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
    }
    
    ///缩点
    if (low[u]==dfn[u])
    {
        bcc_cut++;
        int x;
        while (1)
        {
            x=s.top();
            s.pop();
            bcc[x]=bcc_cut;
            if (x==u) break;
        }
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) g[i].clear();
    bcc_cut=dfs_cut=0;
    while (m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,-1);
    for (int u=1;u<=n;u++)
    {
        for (int j=0;j<g[u].size();j++)
        {
            int v=g[u][j];
            if (bcc[u]!=bcc[v])
            {
                in[bcc[u]]++;
                in[bcc[v]]++;
            }
        }
    }
    int ans=0;
    for (int i=1;i<=bcc_cut;i++)
    {
        if (in[i]==2) ans++;
    }
    printf("%d
",(ans+1)/2);
}