---
tags: uva
---
# Uva12783 - Weak Links
## 題目大意
給一無向圖，問是否某一個 edge 斷開會造成連結的兩點無法相連，列出各束及所有 edge
## 重點觀念
- 參考 https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/uva-12783---weak-links
## 分析
- 只需確認此條 edge 之外是否還有其他條可以相連(通過其他 node) 就能確定
## 程式題目碼

#include <string.h>

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> graph[1024];
vector<pair<int, int> > bridge;
bool visit[1024];
int depth[1024];

int dfs(int cur, int past, int dep) {
    visit[cur] = true, depth[cur] = dep;
    int back = 0x3f3f3f3f;
    for (auto i = graph[cur].begin(); i != graph[cur].end(); i++) {
        if (*i == past) {
            continue;
        }
        if (!visit[*i]) {
            int b = dfs(*i, cur, dep + 1);
            if (b > dep) {
                bridge.push_back(make_pair(cur, *i));
            }
            back = min(back, b);
        } else {
            back = min(back, depth[*i]);
        }
    }
    return back;
}

int main() {
    int n, m;
    while (cin >> n >> m, n > 0) {
        for (int i = 0; i < n; i++) {
            graph[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int start, end;
            cin >> start >> end;

            graph[start].push_back(end);
            graph[end].push_back(start);
        }

        bridge.clear();

        memset(visit, false, sizeof(visit));
        memset(depth, 0, sizeof(depth));

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                dfs(i, -1, 0);
            }
        }
        for (int i = 0; i < bridge.size(); i++) {
            if (bridge[i].first > bridge[i].second) {
                swap(bridge[i].first, bridge[i].second);
            }
        }
        sort(bridge.begin(), bridge.end());

        cout << bridge.size();

        for (auto i = bridge.begin(); i != bridge.end(); i++) {
            cout << " " << (*i).first << " " << (*i).second;
        }
        cout << endl;
    }

    return 0;
}