【HDU3394】Railway

描述
有一个公园有n个景点，公园的管理员准备修建m条道路，并且安排一些形成回路的参观路线。


如果一条道路被多条道路公用，那么这条路是冲突的；


如果一条道路没在任何一个回路内，那么这条路是不冲突的。


问分别有多少条有冲突的路和没有冲突的路 ？


输入
有若干个测试点


每个测试点第一行2个整数n(<=10000)，m<=100000


接下来m行，每行2个数u，v表示u到v有条路 两点没有重边


最后一个测试点用2个0，表示输入结束


输出
若干行，每行表示一个测试点的输出，2个数，分别是有多少冲突路数量，不冲突路的数量


样例输入 
8 10
0 1
1 2
2 3
3 0
3 4
4 5
5 6
6 7
7 4
5 7
0 0
样例输出 

5 1

分析：模板呀。点双连通分量+割边。

#include<bits/stdc++.h>
using namespace std;

#define N 10001

int n,m,p,r,root,cnt=0,cot=0,ans=0,cut=0;
int first[N],dfn[N],low[N],flag[N];

struct email
{
    int u,v;
    int nxt;
}e[N*100];
stack <email> stak;
set <int> bcc;
void add(int u,int v)
{
    e[++cnt].nxt=first[u];first[u]=cnt;
    e[cnt].u=u;e[cnt].v=v;
}

void init()
{
    cnt=0;cot=0;cut=0;ans=0;
    memset(first,0,sizeof(first));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    while(!stak.empty())
        stak.pop();
}

void dfs(int u,int fa)
{
    int son=0;
     dfn[u]=low[u]=++cot;
    for(int i=first[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)    continue;
        if(!dfn[v])
        {
            stak.push(e[i]);
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                email tmp;
                int num=0;
                bcc.clear();
                do
                {
                    num++;
                    tmp=stak.top();
                    stak.pop();
                    bcc.insert(tmp.u);
                    bcc.insert(tmp.v);
                }while(tmp.u!=u||tmp.v!=v);
                if(num>bcc.size()) 
                    ans+=num;
            }
            if(low[v]>dfn[u]) 
                ++cut;
        } 
        else if(dfn[v]<dfn[u])
            {
                stak.push(e[i]);
                low[u]=min(low[u],dfn[v]);
            }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }    
        dfs(1,-1);   
        printf("%d %d
",cut,ans);  
    }
    return 0;
}