hdu 3394 Railway 点双连通分量 + 桥

hdu 3394 Railway
双连通分量

题意：给一个无向图。如果至少有两个环共用了一些边，那么这些边被认为是“冲突边”。如果一些边不在任何一个环中，这些边被认为是“多余边”。你要找出这个图中有多少“多余边”和“冲突边”然后输出条数。另外这图不一定是连通的

1.“多余边”不在任何一个环中，那么多余边一定是桥，所以统计这个无向图中有多少桥即可

2.“冲突边”有多少，这个有点费劲，但是不难想到。如果一个环比较特殊，n个点刚好n条边，例如（1,2）（2,3）（1，3）这种环，这个环内，一条“冲突边”都没有，但是如果一个环内的边数大于点数，那么这个环内所有边都是“冲突边”（真可惜，因为有多出来的那些边后，相当于把最外面的大环分割成了内部的几个小环，这些小环和小环之间，小环和大环之间一定会公用一些边，这些边就是“冲突边”，而且可以发现，所有边都会被公用，太可惜了......），例如sample里面的(5,6)(5,4)(6,7)(4,7)(5,7)，相当于最外面的大环<6,5,4,7,6> ， 而里面的边(5,7)把这个大环分割成了两个小环。因为是求环,所以求的是点双连通分量。

所以做法就是，求出这个无向图有多少个点双连通分量，对于每个点双连通分量，如果内部的边数>点数，那么这些边全部都是冲突边

#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);
    }
}