無向連結グラフにおける橋（割辺）の検出アルゴリズムを解説します。HDU 4738およびHDU 3849の問題例を用いて実装方法を示します。

HDU 4738では、N個の島とM本の橋からなるグラフを扱います。各橋には兵士数が設定されており、単一の橋を破壊してグラフを非連結にするための最小要員数を算出します。グラフが既に非連結の場合は0を出力します。橋が存在しない場合は-1を返します。兵士数が0の場合は1人を派遣する必要があります。

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

const int MAX_NODES = 1111;
const int INF = 999999999;

struct Edge {
    int source;
    int target;
    int soldiers;
    int next;
};

Edge graphEdges[MAX_NODES * MAX_NODES * 2];
int adjacencyList[MAX_NODES];
int discoveryTime[MAX_NODES];
int lowLink[MAX_NODES];
int componentId[MAX_NODES];
int nodeCount, edgeIndex, timestamp, componentCount;
bool inStack[MAX_NODES];
stack<int> nodeStack;

void initializeGraph() {
    edgeIndex = 0;
    memset(adjacencyList, -1, sizeof(adjacencyList));
}

void addEdge(int u, int v, int w) {
    graphEdges[edgeIndex].source = u;
    graphEdges[edgeIndex].target = v;
    graphEdges[edgeIndex].soldiers = w;
    graphEdges[edgeIndex].next = adjacencyList[u];
    adjacencyList[u] = edgeIndex++;
}

void tarjan(int current, int parentEdgeIndex) {
    discoveryTime[current] = lowLink[current] = ++timestamp;
    inStack[current] = true;
    nodeStack.push(current);
    for (int i = adjacencyList[current]; i != -1; i = graphEdges[i].next) {
        if (i == (1 ^ parentEdgeIndex)) continue;
        int neighbor = graphEdges[i].target;
        if (discoveryTime[neighbor] == 0) {
            tarjan(neighbor, i);
            lowLink[current] = min(lowLink[current], lowLink[neighbor]);
        } else if (inStack[neighbor]) {
            lowLink[current] = min(lowLink[current], discoveryTime[neighbor]);
        }
    }
    if (lowLink[current] == discoveryTime[current]) {
        componentCount++;
        int node;
        do {
            node = nodeStack.top();
            nodeStack.pop();
            inStack[node] = false;
            componentId[node] = componentCount;
        } while (node != current);
    }
}

int countComponents() {
    timestamp = componentCount = 0;
    memset(discoveryTime, 0, sizeof(discoveryTime));
    memset(lowLink, 0, sizeof(lowLink));
    int components = 0;
    for (int i = 1; i <= nodeCount; i++) {
        if (discoveryTime[i] == 0) {
            components++;
            tarjan(i, -1);
        }
    }
    return components;
}

int main() {
    int edgeCountInput;
    while (scanf("%d %d", &nodeCount, &edgeCountInput), nodeCount || edgeCountInput) {
        initializeGraph();
        for (int i = 0; i < edgeCountInput; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            addEdge(a, b, c);
            addEdge(b, a, c);
        }
        int connectedComponents = countComponents();
        int minSoldiers = INF;
        for (int i = 0; i < edgeIndex; i += 2) {
            int u = graphEdges[i].source;
            int v = graphEdges[i].target;
            if (componentId[u] != componentId[v]) {
                minSoldiers = min(minSoldiers, graphEdges[i].soldiers);
            }
        }
        if (connectedComponents > 1) {
            printf("0\n");
        } else if (minSoldiers == INF) {
            printf("-1\n");
        } else {
            if (minSoldiers == 0) {
                printf("1\n");
            } else {
                printf("%d\n", minSoldiers);
            }
        }
    }
    return 0;
}

HDU 3849では、文字列をノードとするグラフの橋を特定し、各橋のノード名を出力します。以下の実装例を参照してください。

#include <cstring>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_NODES = 10009;
const int INF = 999999999;

struct Edge {
    int source;
    int target;
    int next;
};

Edge graphEdges[MAX_NODES * 30];
int adjacencyList[MAX_NODES];
int discoveryTime[MAX_NODES];
int lowLink[MAX_NODES];
int bridgeIndices[MAX_NODES];
int nodeCount, edgeIndex, timestamp, bridgeCount, connectedComponents;
char nodeName[MAX_NODES][33];

void initializeGraph() {
    edgeIndex = 0;
    memset(adjacencyList, -1, sizeof(adjacencyList));
}

void addEdge(int u, int v) {
    graphEdges[edgeIndex].source = u;
    graphEdges[edgeIndex].target = v;
    graphEdges[edgeIndex].next = adjacencyList[u];
    adjacencyList[u] = edgeIndex++;
}

void tarjan(int current, int parent) {
    discoveryTime[current] = lowLink[current] = ++timestamp;
    for (int i = adjacencyList[current]; i != -1; i = graphEdges[i].next) {
        int neighbor = graphEdges[i].target;
        if (neighbor == parent) continue;
        if (discoveryTime[neighbor] == 0) {
            tarjan(neighbor, current);
            lowLink[current] = min(lowLink[current], lowLink[neighbor]);
            if (lowLink[neighbor] > discoveryTime[current]) {
                bridgeIndices[bridgeCount++] = i;
            }
        } else {
            lowLink[current] = min(lowLink[current], discoveryTime[neighbor]);
        }
    }
}

void processGraph() {
    timestamp = bridgeCount = connectedComponents = 0;
    memset(discoveryTime, 0, sizeof(discoveryTime));
    memset(lowLink, 0, sizeof(lowLink));
    for (int i = 1; i <= nodeCount; i++) {
        if (discoveryTime[i] == 0) {
            connectedComponents++;
            tarjan(i, -1);
        }
    }
}

int main() {
    int testCases;
    scanf("%d", &testCases);
    while (testCases--) {
        scanf("%d %d", &nodeCount, &edgeIndex);
        initializeGraph();
        map<string, int> stringToIndex;
        int currentIndex = 1;
        for (int i = 0; i < edgeIndex; i++) {
            char str1[33], str2[33];
            scanf("%s %s", str1, str2);
            if (stringToIndex.find(str1) == stringToIndex.end()) {
                stringToIndex[str1] = currentIndex++;
                strcpy(nodeName[stringToIndex[str1]], str1);
            }
            if (stringToIndex.find(str2) == stringToIndex.end()) {
                stringToIndex[str2] = currentIndex++;
                strcpy(nodeName[stringToIndex[str2]], str2);
            }
            int u = stringToIndex[str1];
            int v = stringToIndex[str2];
            addEdge(u, v);
            addEdge(v, u);
        }
        processGraph();
        if (connectedComponents > 1) {
            printf("0\n");
            continue;
        }
        sort(bridgeIndices, bridgeIndices + bridgeCount);
        printf("%d\n", bridgeCount);
        for (int i = 0; i < bridgeCount; i++) {
            int edgePos = bridgeIndices[i];
            int u = graphEdges[edgePos].source;
            int v = graphEdges[edgePos].target;
            printf("%s %s\n", nodeName[u], nodeName[v]);
        }
    }
    return 0;
}