UVA 796 Critical Links(Connected graph Bridge)

Description

给出无向图求桥，可能含有重边

Analyze

不在环里的(双向)边都是桥

利用Tarjan算法得到的

times[u]：点u第一次被访问的时间

low[v]：点v所在连通分量中第一个被搜到的点的第一次被访问的时间

若边(u, v)在某个环里，low[v] <= times[u]

反过来，if(low[v] > times[u])说明这条边是桥

另外注意：1. 重边都不是桥。2.添边的时候反向边要紧跟原边(因为用到了e[i].flag = e[i ^ 1].flag = 1;)

Code

#include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int N = 11000;
const int M = 110000;

int n, cnt, tot, bridge, head[N], low[N], times[N];
map<int, map<int, int> > mp;

struct edge
{
    bool flag;
    int u, v, pre;
} e[M];

void add(int u, int v)
{
    e[cnt].flag = 0;
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].pre = head[u];
    head[u] = cnt++;
}

void Tarjan(int x, int pre)
{
    low[x] = times[x] = ++tot;
    for(int i = head[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(to == pre)
            continue;
        if(!times[to])
        {
            Tarjan(to, x);
            low[x] = min(low[x], low[to]);
            if(low[to] > times[x])
            {
                bridge++;
                e[i].flag = e[i ^ 1].flag = 1;///must add edge together!
            }
        }
        else
            low[x] = min(low[x], times[to]);
    }
}

int main()
{
    while(~scanf("%d", &n))
    {
        if(n == 0)
        {
            cout << "0 critical links\n\n";
            continue;
        }

        cnt = tot = bridge = 0, mp.clear();
        memset(low, 0, sizeof(low));
        memset(times, 0, sizeof(times));
        memset(head, -1, sizeof(head));

        int u, v, num;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d (%d)", &u, &num);
            while(num--)
            {
                scanf("%d", &v);
                if(v <= u)
                    continue;
                add(u, v), mp[u][v]++;
                add(v, u), mp[v][u]++;
            }
        }

        for(int i = 0; i < n; ++i)
            if(!times[i])
                Tarjan(i, -1);

        if(bridge == 0)
        {
            cout << "0 critical links\n\n";
            continue;
        }

        cout << bridge << " critical links\n";
        priority_queue<P, vector<P>, greater<P> > q;
        for(int i = 0; i < cnt; i += 2)
            if(mp[ e[i].u ][ e[i].v ] == 1 && e[i].flag)
                q.push(P(min(e[i].u, e[i].v), max(e[i].u, e[i].v)));

        P now;
        while(!q.empty())
        {
            now = q.top();
            q.pop();
            cout << now.first << " - " << now.second << '\n';
        }
        putchar('\n');
    }
    return 0;
}