<题目连接>
题目大意：
给你一个(保证输入无重边,无自环)无向图,然后有下面Q条询问,每条询问为:问你u点与v点之间有几条(除了首尾两点外,其他点不重复)的路径.如果有0条或1条输出0或1,如果有2条以上,输出”two or more”.
解题分析：
我们可以用并查集判断两点之间是否有路径相连通，如果两点不连通，则直接输出0即可。至于判断两点之间有几条不重复的路径相连，则是通过这两点是否属于同一点双连通分量来判断。不过需要注意的是，我们应该排除只有两个点的点双连通分量这一特殊情况。所以综上，只要待查询的两点属于点数大于2的点双连通分量，则直接输出"two or more"(在已经判断这两点连通的情况下)，否则输出"one"。
#include <bits/stdc++.h> using namespace std; #define pb push_back #define rp(i, s, t) for (int i = s; i < t; i++) #define clr(a, b) memset(a, b, sizeof(a)) const int N = 5e3 + 10; int n, m, q; int tot, bcc; int dfn[N], low[N], col[N], fa[N]; //col[i]表示的是这个点当前所属的点双连通分量的编号 vector<int> G[N], BCC[N], bl[N]; //bl[i]表示第i个节点属于的所有点双连通分量编号 struct Edge { int u, v; Edge(int u = 0, int v = 0) : u(u), v(v) {} }; void init() { bcc = tot = 0; clr(dfn, 0);clr(col, 0); clr(fa, -1); rp(i, 0, n) G[i].clear(), bl[i].clear(); } stack<Edge> stk; void Tarjan(int u, int fa) { low[u] = dfn[u] = ++tot; rp(i, 0, G[u].size()) { int v = G[u][i]; if (v == fa) continue; Edge e = Edge(u, v); if (!dfn[v]) { stk.push(e); Tarjan(v, u); low[u] = min(low[v], low[u]); if (low[v] >= dfn[u]) { //割点 bcc++; BCC[bcc].clear(); while (true) { //将栈中所有属于当前点双连通分量的点全部标记，注意，栈内存的是边 Edge x = stk.top(); stk.pop(); int st = x.u, ed = x.v; if (col[st] != bcc) { BCC[bcc].pb(st); //将u加入当前点双连通分量的节点集 col[st] = bcc; //标记u点当前所述的点双连通分量编号，防止在遍历同一点双连通分量的过程中重复将点标记 bl[st].pb(bcc); //一个点可能属于多个点双连通分量,bl[u]存储的是u点所属的多个点双连通分量 } if (col[ed] != bcc) { BCC[bcc].pb(ed); col[ed] = bcc; bl[ed].pb(bcc); } if (st == u && ed == v) break; } } } else if (dfn[v] < dfn[u]) { stk.push(e); low[u] = min(low[u], dfn[v]); } } } int find(int i) { if (fa[i] == -1) return i; return fa[i] = find(fa[i]); } int main() { int ncase = 0; while (~scanf("%d%d%d", &n, &m, &q) && n) { init(); while (m--) { int u, v; scanf("%d%d", &u, &v); G[u].pb(v), G[v].pb(u); u = find(u), v = find(v); //并查集加边 if (u != v) fa[u] = v; } rp(i, 0, n) if (!dfn[i]) Tarjan(i, -1); printf("Case %d: ", ++ncase); while (q--) { int u, v; scanf("%d%d", &u, &v); if (find(u) != find(v)) printf("zero "); //如果这两点不连通，直接输出0 else { bool flag = false; for (int i = 0; i < bl[u].size() && !flag; i++) //遍历u和v所属的点双连通分量点集，判断是否有点双连通分量同时包含u和v for (int j = 0; j < bl[v].size() && !flag; j++) { if (bl[u][i] == bl[v][j]) { //如果存在这样的点双连通分量 int ord = bl[u][i]; // ord代表该点双连通分量的编号 if (BCC[ord].size() > 2) //要如果该点双连通分量中点数>2，才能说明u和v之间一定有2条即两条以上的道路 puts("two or more"), flag = true; } } if (!flag) puts("one"); //如果不存在点数>2的点双连通分量同时包含u和v，则说明u和v之间只有一条边相连 } } } }
2018-12-02