圆方树

· · 个人记录

圆方树

学习链接 ： 圆方树

易错点

  1. 理解概念， 圆方树是把每个点双新建成了方点，原来的点是圆点。
  2. 理解判定条件 low[v] == dfn[u]
  3. 注意公共点不出栈
  4. 注意每次tarjan后把栈顶减去。
int n, m, cnt, fa[N<<1], ans[N], tot;
vector<int> g[N<<1], t[N<<1];
int dfn[N], low[N], dfs_clock, sta[N], top;
void tarjan(int u) {
    low[u] = dfn[u] = ++dfs_clock;
    sta[++top] = u;
    for(register int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v] == dfn[u]) {
                ++cnt;
                for(int x = 0; x != v; --top) {
                    x = sta[top];
                    t[cnt].push_back(x);
                    t[x].push_back(cnt);
                }
                t[cnt].push_back(u);
                t[u].push_back(cnt);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

学习心得

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m;
struct edge { int to, next, w; } e[M];
int head[N], cnt;
void add(int x, int y, int z) {
    e[++cnt].to = y, e[cnt].next = head[x], e[cnt].w = z, head[x] = cnt;
} 
int dfn[N], low[N], dfs_clock, sta[N], top;
void tarjan(int u) {
    dfn[u] = low[u] = ++dfs_clock, sta[++top] = u;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if(!dfn[v]) {
            tarjan(v), low[u] = min(low[u], low[v]);
            if(low[v] == dfn[u]) {
                ++n; int x = sta[top];
                while(x != u) {
                    add(x, n, 0), add(n, x, 0);
                    x = sta[--top];
                }
                add(u, n, 0), add(n, u, 0);// 别忘了加点
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    for(int i = 1; i <= n; ++i) if(dfn[i]) tarjan(i);

    return 0;
}

圆方树的应用

已经学完了知识，该来道例题了。

题目链接 ： [ZJOI2004]嗅探器

题解链接 ： 嗅探器

这篇题解已经讲的很清晰了，不过还有几个注重点，首先需要思考什么时候可以取答案,为什么可以这样就是对的，而不是一味平感觉，只看结论。

下面奉上我自己觉的很好的码风，既不那么压行，有简单易懂。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5, M = 2e6 + 5;
int n, nn; int head[N], cnt; int start, target;
struct edge { int to, next; } e[M];
void add(int x, int y) { e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt; }
int dfn[N], low[N], sta[N], top, dfs_clock;
vector<int> g[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++dfs_clock, sta[++top] = u;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if(!dfn[v]) {
            tarjan(v); low[u] = min(low[u], low[v]);
            if(low[v] == dfn[u]) {
                nn++;
                while(1) {
                    int x = sta[top--];
                    g[x].push_back(nn), g[nn].push_back(x);
                    if(x == v) break;
                } g[u].push_back(nn), g[nn].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);        
    }
}
void dfs(int u, int fa, int ans) {
    if(u == target) {
        if(ans == 0) cout << "No solution";
        else cout << ans;
        exit(0);
    }
    if(u != start && u <= n && g[u].size() > 1) ans = ans == 0 ? u : min(ans, u);
    for(int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i]; if(v == fa) continue; dfs(v, u, ans);
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n; int x, y; nn = n;
    while(cin >> x >> y && x != 0 && y != 0) add(x, y), add(y, x);
    cin >> start >> target;
    tarjan(start);
    if(dfn[target] == 0) return cout << "No solution", 0;
    dfs(start, 0, 0);
    return 0;
}