POJ 3895 Cycles of Lanes（無向圖最大環 DFS）

POJ 3895 Cycles of Lanes - 無向圖最大簡單環

給定無向連通圖，每條邊屬於至多一個簡單環。求最大環長度。

關鍵性質

每條邊屬於至多一個簡單環 ⇒ 圖是仙人掌圖或類似結構。DFS 即可找到所有環。

DFS 找環算法

• 記錄 dfn[u] = 訪問時間戳
• 遇到已訪問非父節點 ⇒ 發現環，長度 = dfn[u] - dfn[v] + 1
• 因為每條邊最多在一個環中，不會重複計算

完整代碼實現（鄰接表 + DFS）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 4500;

struct Edge { int to, next; } e[MAXN<<2];
int head[MAXN], ecnt;
int dfn[MAXN], timer, ans;

void addEdge(int u, int v) {
    e[ecnt] = {v, head[u]}; head[u] = ecnt++;
}

void dfs(int u, int parent) {
    dfn[u] = ++timer;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == parent) continue;
        if (!dfn[v]) dfs(v, u);
        else if (dfn[v] < dfn[u])  // 回邊，找到環
            ans = max(ans, dfn[u] - dfn[v] + 1);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        memset(head, -1, sizeof(head)); ecnt = 0;
        for (int i = 0; i < m; i++) {
            int u, v; scanf("%d%d", &u, &v);
            addEdge(u, v); addEdge(v, u);
        }
        memset(dfn, 0, sizeof(dfn));
        timer = 0; ans = 0;
        dfs(1, 0);
        if (ans < 3) ans = 0;  // 環長度至少 3
        printf("%d\n", ans);
    }
    return 0;
}

避坑經驗：鄰接矩陣超內存

作者嘗試用 mp[5000][5000] 和 vis[5000][5000]，內存 5000² × 4B ≈ 100MB 超限。必須用鄰接表。

複雜度分析

• 時間：O(N + M)
• 空間：O(N + M)