Codeforces - 962F - Simple Cycles Edges（Tarjan 求點雙）

題目連結：https://codeforces.com/contest/962/problem/F

6.1 題意

給定一個 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \le n\le 10^5) n(1≤n≤105) 個節點和 m ( 0 ≤ m ≤ min ⁡ ( n ( n − 1 ) 2 , 1 0 5 ) ) m(0 \le m \le \min(\frac{n(n-1)}{2},10^5)) m(0≤m≤min(2n(n−1)​,105)) 條邊的無向圖，不含自環和重邊，但可能不連通。

現在需要輸出圖中恰好屬于一個簡單環上的邊。

6.2 解題過程

一個簡單環一定存在于連通分量中，而滿足題意的邊所在的連通分量應該恰好構成一個簡單環。

而我們回憶 Tarjan 算法，會發現求連通分量的過程就是在求簡單環的過程。

那我們應該求點雙呢還是邊雙呢？

回憶簡單環的定義，會發現每個結點隻能經過一次，而點雙恰好可以保證這一點。

是以我們通過 Tarjan 算法求出每個點雙連通分量中的邊集，在維護點棧的同時維護一個邊棧，當周遊到一個新的邊時就将目前邊壓棧，當點棧彈出時，邊棧也跟着彈出。用

vector

存儲每個連通分量中邊的編号。

如何判定一個連通分量中的點恰好構成一個簡單環呢？

如果一個點雙中邊數等于點數，那麼它就是一個簡單環。

那麼這道題也就做完了。

時間複雜度： O ( n log ⁡ n ) O(n \log n) O(nlogn)。

6.3 錯誤點

1. 按照自己的寫法，存邊是按照 ( 0 , 1 ) (0,1) (0,1)、 ( 2 , 3 ) (2,3) (2,3) 這樣的點對存儲的。是以處理點雙時，如果目前邊的編号為 i d id id，則強制按照 i d ∣ 1 id | 1 id∣1 來将邊存入到連通分量中，這樣可以防止同一條無向邊重複計算。
2. 之前采用過比較麻煩的方法來判斷一個點雙是否為簡單環，例如通過每個點的度。這樣很容易出錯。最便捷的方法就是判斷點數是否等于邊數。

6.4 代碼

int n, m;
int head[maxn], cnt, num, top, tot, top2;
int dfn[maxn], low[maxn], st[maxn], st2[maxn];
bool cut[maxn], vis[maxn];
int mark[maxn], deg[maxn];
vector<int> dcc[maxn], dcc2[maxn];
struct edge
{
    int id, v, nxt;
} Edge[2 * maxn];
void init()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
    num = 0;
    top = 0;
    tot = 0;
}
void addedge(int u, int v, int id)
{
    Edge[cnt].id = id;
    Edge[cnt].v = v;
    Edge[cnt].nxt = head[u];
    head[u] = cnt++;
}
void tarjan(int id, int rt) {
    dfn[id] = low[id] = ++num;
    st[++top] = id;
    if (id == rt && head[id] == -1) {
        dcc[++tot].pb(id);
        return;
    }
    int flag = 0;
    for (int i = head[id]; i != -1; i = Edge[i].nxt) {
        int v = Edge[i].v;
        if (vis[i] || vis[i ^ 1]) continue;
        vis[i] = true;
        st2[++top2] = i;
        if (!dfn[v]) {
            tarjan(v, rt);
            low[id] = min(low[id], low[v]);
            if (low[v] >= dfn[id]) {
                flag++;
                if (id != rt || flag > 1) cut[id] = true;
                tot++;
                int z;
                do {
                    z = st[top--];
                    dcc[tot].pb(z);
                } while (z != v);
                do {
                    z = st2[top2--];
                    dcc2[tot].pb(z | 1);
                } while (z != i);
                dcc[tot].pb(id);
            }
        } else {
            low[id] = min(low[id], dfn[v]);
        }
    }
}
set<int> ans;
int main()
{
    int u, v;
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        addedge(u, v, i);
        addedge(v, u, i);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, i);
        }
    }
    int col = 0;
    for (int i = 1; i <= tot; i++) {
        ++col;
        for (auto id: dcc[i]) {
            deg[id] = 0;
        }
        sort(dcc2[i].begin(), dcc2[i].end());
        dcc2[i].erase(unique(dcc2[i].begin(), dcc2[i].end()), dcc2[i].end());
        bool isok = (dcc[i].size() == dcc2[i].size());
        if (!isok) {
            continue;
        }
        for (auto id: dcc2[i]) {
            ans.insert(Edge[id].id);
        }
    }
    printf("%d\n", (int)ans.size());
    for (auto x: ans) {
        printf("%d ", x);
    }
    return 0;
}