hiho 學習日記：hiho一下 第五十三周（邊的雙連通分量）

http://hihocoder.com/contest/hiho53/problem/1

求出邊的雙聯通分量

與求割點與割邊類似，求邊的雙聯通分量找的是橋，有m橋，那麼就有m+1的分組。

而分組有點類似割邊，如果一個分組中存在割邊那麼這個分組就不是分組，是以這張圖的割邊就是分組的邊界，不包括在分組中，而low[u] == cur[u]正是割邊所在的點，這是利用棧和DFS，把u後面入棧的點全部劃分成同一分組，這樣就寫完了

AC代碼：

#include <bits/stdc++.h>

using namespace std;
#define LL long long
const int Mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const double eps = 0.00000001;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v, next;
}edge[maxn << 1];

int tot, head[maxn];
int parent[maxn], vis[maxn], low[maxn], cur[maxn], trace[maxn];
int top, sta[maxn], cnt;

void init() {
    cnt = top = tot = 0;
    memset(head, -1, sizeof(head));
    memset(parent, -1, sizeof(parent));
    memset(vis, 0, sizeof(vis));
}

void addEdge(int u, int v) {
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot ++;

    edge[tot].v = u;
    edge[tot].next = head[v];
    head[v] = tot ++;
}

void DFS(int u) {
    static int counter = 0;
    int child = 0;
    vis[u] = 1;
    cur[u] = low[u] = ++counter;
    sta[++ top] = u;
    for (int i = head[u]; i + 1; i = edge[i].next) {
        int v = edge[i].v;
        if(!vis[v]) {
            child ++;
            parent[v] = u;
            DFS(v);
            low[u] = min(low[u], low[v]);
            if(cur[u] < low[v]) {
                cnt ++;
                //printf("bridge: %d %d\n", u, v);
            }
        }else if(v != parent[u])
            low[u] = min(low[u], cur[v]);
    }
    if(low[u] >= cur[u]) {
        int tt = top;
        int minn = u;
        while(sta[tt] != u) {
            minn = min(minn, sta[tt]);
            tt --;
        }
        while(sta[top] != u) {
            trace[sta[top]] = minn;
            top --;
        }
        if(sta[top] == u) {
            trace[u] = minn;
            top --;
        }
    }
}

int main()
{
    init();
    int N, M;
    cin >> N >> M;
    while(M --) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    DFS(1);
    cout << cnt + 1<< endl;
    for (int i = 1; i <= N; i ++)
        cout << trace[i] << " ";
    cout << endl;
    return 0;
}