Financial Crisis HDU

原题链接

  • 题解：算是比较心累的一道题了，发现复杂的图论题尤其是涉及联通分量，就是大模拟+分类讨论。题中意思是，问两个点，是否能有两条不同路径。不同是指没有经过同一个点除了起点和终点。所以如果在同一个连通分量中，并且连通分量的大小大于2，那么必然是两条及以上。如果两个点不在一个集合，即没有道路。如果两个点，这两个点所在的所有连通分量，没有满足，相同并且大小大于2，那么这两个点之间只有一条路径。
  1. 首先第一个对我来说不会的是，如何使每个连通分量包含他们里面的点？即表示有个割点 (a) 在 (A) 和 (B) 中，从 (A) 中得到 (a) 信息，从 (B) 中得到 (a) 信息。那么我们这个栈就不是储存点的了，是储存的是属于这个连通分量的边，然后把边上所有点都加进来就行了，注意，那么如果边 (a-b) 和 (b-c) 都加，那么 (b) 就加了两边，连通分量大小会不对，那么就用 (mark) 判一下重复。
if (mark[u] != dcc) 
    id[u].push_back(dcc),sz[dcc]++, mark[u] = dcc;
if (mark[v] != dcc)
    id[v].push_back(dcc), sz[dcc]++, mark[v] = dcc;
  1. 分类讨论时，就直接遍历每个点所在的连通分量，二重 (for) 循环暴力跑，然后就可以判是否存在这两个点都在一个 (size > 2) 的连通分量中了。
  • 代码：
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;
const int N = 101000;
const int M = 401000;
struct edge {
    int u, v;
}e[N];
int h[M], ne[M], to[M], idx;
int dfn[N], low[N], times;
int f[N];
int sz[N];
int mark[N];
int stk[N], top;
int dcc = 0;
int cut[N];
void add(int u, int v) {ne[idx] = h[u], to[idx] = v, h[u] = idx++;}
vector<int>id[N];
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++times;
    
    int cnt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        
        int v = to[i];
        if (!dfn[v]) {
                        e[++top] = {u, v};
            tarjan(v, u);
            cnt++;
            low[u] = min(low[u], low[v]);
            if (dfn[u] <= low[v]) {
                if (u != fa)cut[u] = 1;
                else cut[u] |= (cnt > 1);
                dcc++;
                if (mark[u] != dcc) 
                id[u].push_back(dcc),sz[dcc]++, mark[u] = dcc;
                if (mark[v] != dcc)
                    id[v].push_back(dcc), sz[dcc]++, mark[v] = dcc;
                while (e[top].u != u || e[top].v != v) {
                    int uu = e[top].u;
                    int vv = e[top].v;
                    if (mark[uu] != dcc)
                        id[uu].push_back(dcc), sz[dcc]++, mark[uu] = dcc;
                    if (mark[vv] != dcc)
                        id[vv].push_back(dcc), sz[dcc]++, mark[vv] = dcc;
                    top--;
                }top--;
            }
        } else
            low[u] = min(low[u], dfn[v]);
    }
}
int Find(int x){return f[x] == x?x:f[x] = Find(f[x]);}
void Un(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if (fx == fy)return;
    f[fx] = fy;
}
int cas = 0;
void solve() {
    int n, m, q;
    int cas = 0;
    while (~scanf("%d%d%d", &n, &m, &q)) {
        if (n == 0 && q == 0 && m == 0)break;
        memset(h, -1, sizeof h);
        top = 0;
        dcc = 0;
        memset(id, 0, sizeof id);
        memset(dfn, 0, sizeof dfn);
        memset(sz, 0, sizeof sz);
        memset(mark, 0, sizeof mark);
        idx = times = 0;
        for (int i = 0; i < n; i ++) {
            f[i] = i;
            id[i].clear();
        }
        for (int i = 1; i <= m; i ++) 
        {
            int u, v;scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
            Un(u, v);
        }
        for (int i = 0; i < n; i ++) {
            if (!dfn[i])tarjan(i, i);
        }
        printf("Case %d:
", ++cas);
        while (q--) {
            int u, v;scanf("%d%d", &u, &v);
            int fx = Find(u);
            int fy = Find(v);
            if (fx != fy) {
                puts("zero");
            } else {
                bool f = 0;
                for (auto uu:id[u]) {
                    for (auto vv:id[v]) {
                        if (vv == uu) {
                            if (sz[vv] > 2) {
                                f = 1;
                                puts("two or more");
                            }
                        }
                        if(f)break;
                    }
                    if (f)break;
                }
                if (!f) puts("one");
            }
        }
    }
}
int main() {
    //ios::sync_with_stdio(0);
    int t = 1;//cin >> t;
    while (t--)solve();
    return 0;
}

还有一份精简版的，求割点和点双连通分量。

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;
const int N = 101000;
const int M = 401000;
int h[M], ne[M], to[M], idx;
int dfn[N], low[N], times;
int f[N];
int sz[N];
int stk[N], top;
int dcc = 0;
int cut[N];
void add(int u, int v) {ne[idx] = h[u], to[idx] = v, h[u] = idx++;}
vector<int>bl[N];
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++times;
    stk[++top] = u;
    int cnt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = to[i];
        if (!dfn[v]) {
            tarjan(v, fa), ++cnt;
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (u != fa)cut[u] = 1;
                else cut[u] |= (cnt > 1);
                ++dcc;
                while (1) {
                    bl[stk[top]].push_back(dcc);//可以bl[dcc].push_back(stk[top]);
                    //主要是看自己需要啥,就咋写
                    sz[dcc]++;
                    if (stk[top--] == v)break;//这里确实有点不好理解，就是说，他这团是把当前这一团外面那一团给算上的，下次补一下图咕咕咕。
                }
                bl[u].push_back(dcc);
                sz[dcc]++;
            }
        } else
            low[u] = min(low[u], dfn[v]);
    }
}
int Find(int x){return f[x] == x?x:f[x] = Find(f[x]);}
void Un(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if (fx == fy)return;
    f[fx] = fy;
}
int cas = 0;
void solve() {
    int n, m, q;
    int cas = 0;
    while (~scanf("%d%d%d", &n, &m, &q)) {
        if (n == 0 && q == 0 && m == 0)break;
        memset(h, -1, sizeof h);
        top = 0;
        dcc = 0;
        memset(id, 0, sizeof id);
        memset(dfn, 0, sizeof dfn);
        memset(sz, 0, sizeof sz);
        memset(mark, 0, sizeof mark);
        idx = times = 0;
        for (int i = 0; i < n; i ++) {
            f[i] = i;
            bl[i].clear();
        }
        for (int i = 1; i <= m; i ++) 
        {
            int u, v;scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
            Un(u, v);
        }
        for (int i = 0; i < n; i ++) {
            if (!dfn[i])tarjan(i, i);
        }
        printf("Case %d:
", ++cas);
        while (q--) {
            int u, v;scanf("%d%d", &u, &v);
            int fx = Find(u);
            int fy = Find(v);
            if (fx != fy) {
                puts("zero");
            } else {
                bool f = 0;
                for (auto uu:bl[u]) {
                    for (auto vv:bl[v]) {
                        if (vv == uu) {
                            if (sz[vv] > 2) {
                                f = 1;
                                puts("two or more");
                            }
                        }
                        if(f)break;
                    }
                    if (f)break;
                }
                if (!f) puts("one");
            }
        }
    }
}
int main() {
    //ios::sync_with_stdio(0);
    int t = 1;//cin >> t;
    while (t--)solve();
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Xiao-yan/p/14632026.html