传送门

题意:如果两个点不在一个连通图中,即无路径相连,输出"zero",如果在同一个连通图中,如果两点路径上必经过割点,输出"one",

其余输出"two or more",点双连通分量(第一次接触,之前都做得有向图缩点)

博客传送门

AC代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 5005;
struct edge {
    int from;
    int to;
    int next;
}e[maxn << 2];
struct info {
    int x, y;
    info(int a, int b) {
        x = a; y = b;
    }
};
vector<int>num[maxn];
vector<int>node[maxn];
int head[maxn];
int dfn[maxn];                //时间戳 
int low[maxn];                //最小返祖时间序 
int bcc[maxn];                //点所属的连通分量编号 
int f[maxn];                //父节点 
int tot, cnt, res;
stack<info>s;
inline void clear_set()
{
    tot = cnt = res = 0;
    memset(head, -1, sizeof(head));
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(bcc, 0, sizeof(bcc));
    while (!s.empty())    s.pop();
    for (int i = 0; i < maxn; i++) {
        f[i] = i;
        num[i].clear();
        node[i].clear();
    }
}
inline int find_set(int x)
{
    if (x != f[x]) {
        f[x] = find_set(f[x]);
    }
    return f[x];
}
inline void addedge(int x, int y)
{
    e[tot].from = x;
    e[tot].to = y;
    e[tot].next = head[x];
    head[x] = tot++;
}
inline void tarjan(int x, int fx)
{
    dfn[x] = low[x] = ++cnt;
    for (int i = head[x]; ~i; i = e[i].next) {
        int y = e[i].to;
        if (y == fx)        continue;
        if (!dfn[y]) {
            s.push(info(x, y));
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {//点双连通分量
                res++;
                while (1) {
                    info t = s.top(); s.pop();
                    if (bcc[t.x] != res) {
                        node[res].push_back(t.x);            //当前这个连通分量重加入这个点 
                        bcc[t.x] = res;                        //判重用 
                        num[t.x].push_back(res);            //当前这个点属于哪个连通分量 
                    }
                    if (bcc[t.y] != res) {
                        node[res].push_back(t.y);
                        bcc[t.y] = res;
                        num[t.y].push_back(res);
                    }
                    if (t.x == x && t.y == y)    break;
                }
            }
        }
        else if (dfn[y] < dfn[x]) {
            s.push(info(x, y));
            low[x] = min(low[x], dfn[y]);
        }
    }
}
int main()
{
    int n, m, q, k = 1;
    while (~scanf("%d%d%d", &n, &m, &q)) {
        if (n == 0 && m == 0 && q == 0)        break;
        int x, y;
        clear_set();
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &x, &y);
            addedge(x, y);    addedge(y, x);
            int fx = find_set(x);
            int fy = find_set(y);
            if (fx != fy) {
                f[fx] = fy;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!dfn[i]) {
                tarjan(i, -1);
            }
        }
        printf("Case %d:\n", k++);
        while (q--) {
            scanf("%d%d", &x, &y);
            int fx = find_set(x);
            int fy = find_set(y);
            if (fx != fy) {
                printf("zero\n");
                continue;
            }
            bool flag = false;
            for (int i = 0; i < num[x].size(); i++) {
                for (int j = 0; j < num[y].size(); j++) {
                    if (num[x][i] == num[y][j] && node[num[x][i]].size() > 2) {
                        //有公共所属的双连通分量 并且 该连通分量中点数超过2 构成点双连通 
                        flag = true;
                        goto out;
                    }
                }
            }
        out:
            if (flag == true)        printf("two or more\n");
            else            printf("one\n");
        }
    }
    return 0;
}