hdu 3394 Railway
雙連通分量

題意：給一個無向圖。如果至少有兩個環(huán)共用了一些邊过蹂，那么這些邊被認(rèn)為是“沖突邊”禾进。如果一些邊不在任何一個環(huán)中漱挎，這些邊被認(rèn)為是“多余邊”力细。你要找出這個圖中有多少“多余邊”和“沖突邊”然后輸出條數(shù)睬澡。另外這圖不一定是連通的

1.“多余邊”不在任何一個環(huán)中，那么多余邊一定是橋眠蚂，所以統(tǒng)計這個無向圖中有多少橋即可

2.“沖突邊”有多少煞聪，這個有點費勁，但是不難想到逝慧。如果一個環(huán)比較特殊昔脯，n個點剛好n條邊，例如（1,2）（2,3）（1笛臣，3）這種環(huán)云稚，這個環(huán)內(nèi)，一條“沖突邊”都沒有沈堡，但是如果一個環(huán)內(nèi)的邊數(shù)大于點數(shù)静陈，那么這個環(huán)內(nèi)所有邊都是“沖突邊”（真可惜，因為有多出來的那些邊后诞丽，相當(dāng)于把最外面的大環(huán)分割成了內(nèi)部的幾個小環(huán)鲸拥，這些小環(huán)和小環(huán)之間，小環(huán)和大環(huán)之間一定會公用一些邊僧免，這些邊就是“沖突邊”刑赶，而且可以發(fā)現(xiàn)，所有邊都會被公用懂衩，太可惜了......）撞叨，例如sample里面的(5,6)(5,4)(6,7)(4,7)(5,7)，相當(dāng)于最外面的大環(huán)<6,5,4,7,6> 浊洞， 而里面的邊(5,7)把這個大環(huán)分割成了兩個小環(huán)牵敷。因為是求環(huán),所以求的是點雙連通分量。

所以做法就是沛申，求出這個無向圖有多少個點雙連通分量，對于每個點雙連通分量姐军，如果內(nèi)部的邊數(shù)>點數(shù)铁材，那么這些邊全部都是沖突邊

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int MAXN=10010;
const int MAXE=200010;
struct Node
{
    int to,next,cut;
};
Node edge[MAXE];
int cnt,head[MAXN];
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].cut=0;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
struct Edge
{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
};
stack<Edge> coolector;
int low[MAXN],dfn[MAXN],clocks;
int isCut[MAXN],bccno[MAXN],bcc_cnt;
vector<int> bcc[MAXN];
vector<Edge> edgeCnt[MAXN];
int bridges;
void DFS(int u,int e)
{
    low[u]=dfn[u]=++clocks;
    int child=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(e==(i^1)) continue;
        int v=edge[i].to;
        Edge e(u,v);
        if(dfn[v]==0)
        {
            coolector.push(e);
            child++;
            DFS(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                isCut[u]=true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                edgeCnt[bcc_cnt].clear();
                while(true)
                {
                    Edge tmp=coolector.top();
                    coolector.pop();
                    edgeCnt[bcc_cnt].push_back(tmp);
                    if(bccno[tmp.u]!=bcc_cnt) {bccno[tmp.u]=bcc_cnt;bcc[bcc_cnt].push_back(tmp.u);}
                    if(bccno[tmp.v]!=bcc_cnt) {bccno[tmp.v]=bcc_cnt;bcc[bcc_cnt].push_back(tmp.v);}
                    if(tmp.u==u&&tmp.v==v) break;
                }
            }
            if(low[v]>dfn[u])
            {
                edge[i].cut=1;
                edge[i^1].cut=1;
                bridges++;
            }
        }
        else if(dfn[v]<dfn[u])
        {
            coolector.push(e);
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(e<0&&child==1) isCut[u]=0;
}
void find_cc(int n)
{
    memset(isCut,0,sizeof(isCut));
    memset(bccno,0,sizeof(bccno));
    memset(dfn,0,sizeof(dfn));
    clocks=bcc_cnt=bridges=0;
    for(int i=0;i<n;i++)
    {
        if(dfn[i]==0)
        {
            DFS(i,-1);
        }
    }
}
void work(int n)
{
    find_cc(n);
    int edges=0;
    for(int i=1;i<=bcc_cnt;i++)
    {
        if(edgeCnt[i].size()>bcc[i].size())
        {
            edges+=edgeCnt[i].size();
        }
    }
    printf("%d %d\n",bridges,edges);
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addEdge(a,b);
            addEdge(b,a);
        }
        work(n);
    }
}