POJ3177：Redundant Paths——题解

http://poj.org/problem?id=3177

明显要求桥的一道题。

（因为有桥就说明只能从那一条路走，换句话说就是只有一种方法）

求完桥后按照结论（加几条边成双连通图的结论，不会请baidu）就可以输出ans啦！

（为此学了一下新的桥的求法……原来的那个常数太大了）

#include<stack>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

inline int read(){

    int x=,w=;char ch=;

    while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*w;

}

const int maxn=;

int cnt=,head[maxn];

struct node{

    int w;

    int ed;

    int nxt;

    int st;

}edge[];

void add(int u,int v){

    cnt++;

    edge[cnt].ed=v;

    edge[cnt].st=u;

    edge[cnt].nxt=head[u];

    head[u]=cnt;

    return;

}

bool bridge[];

int dfn[maxn];

int low[maxn];

bool instack[maxn];

int fa[maxn];

int from[maxn];

int indeg[maxn];

int t=;

void tarjan(int u){

    t++;

    dfn[u]=t;

    low[u]=t;

    for(int i=head[u];i;i=edge[i].nxt){

    if(i==(from[u]^))continue;

    int v=edge[i].ed;

    if(!dfn[v]){

        from[v]=i;

        tarjan(v);

        low[u]=min(low[u],low[v]);

        if(low[v]>dfn[u])bridge[from[v]]=bridge[from[v]^]=;

    }else{

        low[u]=min(low[u],dfn[v]);

    }

    }

    return;

}

int find(int a){

    if(fa[a]==a)return a;

    return fa[a]=find(fa[a]);

}

int main(){

    int f=read();

    int r=read();

    for(int i=;i<=r;i++){

    int u=read();

    int v=read();

    add(u,v);

    add(v,u);

    }

    tarjan();

    for(int i=;i<=f;i++)fa[i]=i;

    for(int i=;i<=cnt;i+=){

    if(!bridge[i])fa[find(edge[i].st)]=find(edge[i].ed);

    }

    for(int i=;i<=cnt;i+=){

    if(bridge[i])indeg[find(edge[i].st)]++,indeg[find(edge[i].ed)]++;

    }

    int leaf=;

    for(int i=;i<=f;i++){

    if(find(i)==i){

        if(indeg[i]==)leaf++;

    }

    }

    printf("%d\n",(leaf+)/);

    return ;

}