HDU 3849 By Recognizing…(求无向图的桥数目)

HDU 3849 By Recognizing…(求无向图的桥数目)

http://acm.hdu.edu.cn/showproblem.php?pid=3849

题意:给你一个无向图(可能不连通,但是无自环,无重边),要你输出图中的每条桥边,要求按输入边的顺序输出.

分析:

由于图可能不连通,所以我们只用tarjan(1,-1)即可.然后判断是否还有节点的pre值==0.如果存在这种点,那么该图不连通.

输出每条桥不难,直接用刘汝佳训练指南的模板即可.有点小麻烦的是题目给的边不是数字对,而是两个字符串对.且需要按输出边的顺序输出桥边.

代码中我用map来实现一个字符串到点编号的映射,那么一个输入边就是由两个字符串节点node组成的了.我们先求完所有节点的low值.然后在退出tarjan()函数后,重新扫描每一条边的两个节点u和v的low和pre值.若low[u]>pre[v]||low[v]>pre[u] 那么(u,v)边一定是桥.(仔细想想这个结论)

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
const int maxm=100000+10;
int n,m;
struct node
{
    char s[20];
    bool operator <(const node& rhs)const
    {
        return strcmp(s,rhs.s)<0;
    }
};
map<node,int> mp;//将字符串node映射成节点编号
struct Edge
{
    node u,v;
    bool flag;//标记该边是不是桥
}e[maxm];
vector<int> G[maxn];
int pre[maxn],low[maxn];
int dfs_clock;
void tarjan(int u,int fa)
{
    low[u]=pre[u]=++dfs_clock;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa) continue;
        if(!pre[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u] = min(low[u],pre[v]);
    }
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int id=0;
        scanf("%d%d",&n,&m);
        mp.clear();
        dfs_clock=0;
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=0;i<m;i++)
        {
            e[i].flag=false;
            scanf("%s%s",e[i].u.s,e[i].v.s);
            if(mp.find(e[i].u)==mp.end()) mp[e[i].u]= ++id;
            if(mp.find(e[i].v)==mp.end()) mp[e[i].v]= ++id;
            int x = mp[e[i].u], y=mp[e[i].v];
            G[x].push_back(y);
            G[y].push_back(x);
        }
        tarjan(1,-1);
        bool ok=true;//判断是否连通图
        for(int i=1;i<=n;i++)if(!pre[i])
        {
            ok=false;
            break;
        }
        if(!ok) printf("0\n");
        else
        {
            int ans=0;//计数桥总数
            for(int i=0;i<m;i++)
            {
                int u=mp[e[i].u], v=mp[e[i].v];
                if(low[u]>pre[v]||low[v]>pre[u]) e[i].flag=true,ans++;
            }
            printf("%d\n",ans);
            for(int i=0;i<m;i++)if(e[i].flag)
                printf("%s %s\n",e[i].u.s,e[i].v.s);
        }
    }
    return 0;
}