HDU 3749 Financial Crisis 点双连通分量
给一个无向图, n <5000, m < 10000
然后给出若干的询问（< 1000），问一个点到另一个点之间有多少条路可以走，只需回答有0条还是1条还是多条。注意这些路之间不能有边相同。
方法：
求点的双连通分量。
然后一个割点，有可能属于多个点双连通分量。
所以我们要是用vector把每个点属于的点双连通分量的编号都存起来。
然后我们要计算每个点双连通分量中的边的个数。 因为有那种只有一条边的双连通分量。
计算的方法就是查看边得两个端点所属的双连通分量，如果两个端点有同属于的一个双连通分量，就把对应的数目加1
对于每个询问。
首先看两个点是否连通。用并查集判断即可
然后看是否同属于一个双连通分量。 不属于就只能有一条路
然后同属于一个双连通分量的话，就看边得个数是否大于1。即可
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cmath>#include <map>#include <sstream>#include <queue>#include <vector>#define MAXN 111111#define MAXM 211111#define eps 1e-8#define INF 1000000001using namespace std;int e, tmpdfn, top;int n, m, ind;int vis[MAXM], head[MAXN], dfn[MAXN], low[MAXN], num[MAXM];vector<int>g[MAXN];struct Edge{ int v, next;}edge[MAXM];void add(int u, int v){ edge[e].v = v; edge[e].next = head[u]; head[u] = e++; edge[e].v = u; edge[e].next = head[v]; head[v] = e++;}struct Stack{ int s, e; Stack(){} Stack(int a, int b){s = a; e = b;}}st[MAXM];void init(){ e = tmpdfn = ind = 0; top = -1; memset(vis, 0, sizeof(vis)); memset(dfn, 0, sizeof(dfn)); memset(head, -1, sizeof(head)); memset(num, 0, sizeof(num));}void color(Stack t){ ind++; while(top >= 0) { Stack A = st[top--]; g[A.s].push_back(ind); g[A.e].push_back(ind); if(A.s == t.s && A.e == t.e) break; }}void dfs(int u, int fa){ dfn[u] = low[u] = ++tmpdfn; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(vis[i] == 0) { vis[i] = vis[i ^ 1] = 1; Stack tmp(u, v); st[++top] = tmp; if(!dfn[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) color(tmp); } else if(v != fa) low[u] = min(low[u], dfn[v]); } }}int Q;int uu[MAXM], vv[MAXM];int fa[MAXN];int find(int x){ if(fa[x] == x) return x; int t = find(fa[x]); fa[x] = t; return t;}void join(int u, int v){ int fx = find(u); int fy = find(v); if(fx != fy) fa[fx] = fy;}int main(){ int u, v; int cas = 0; while(scanf("%d%d%d", &n, &m, &Q) != EOF) { if(n == 0 && m == 0 && Q == 0) break; init(); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 0; i < m; i++) { scanf("%d%d", &uu[i], &vv[i]); uu[i]++; vv[i]++; add(uu[i], vv[i]); join(uu[i], vv[i]); } for(int i = 1; i <= n; i++) g[i].clear(); for(int i = 1; i <= n; i++) { if(!dfn[i]) dfs(i, 0); } for(int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end()); for(int i = 1; i <= n; i++) unique(g[i].begin(), g[i].end()); for(int i = 0; i < m; i++) { int sz1 = g[uu[i]].size(); int sz2 = g[vv[i]].size(); int k1 = 0, k2 = 0; while(k1 < sz1 && k2 < sz2) { if(g[uu[i]][k1] > g[vv[i]][k2]) k2++; else if(g[uu[i]][k1] < g[vv[i]][k2]) k1++; else if(g[uu[i]][k1] == g[vv[i]][k2]) { int tmp = g[uu[i]][k1]; num[tmp]++; break; } } } printf("Case %d:\n", ++cas); for(int i = 0; i < Q; i++) { scanf("%d%d", &u, &v); u++; v++; int sz1 = g[u].size(); int sz2 = g[v].size(); int k1 = 0, k2 = 0; int tmp = -1; while(k1 < sz1 && k2 < sz2) { if(g[u][k1] > g[v][k2]) k2++; else if(g[u][k1] < g[v][k2]) k1++; else if(g[u][k1] == g[v][k2]) { tmp = g[u][k1]; break; } } if(find(u) != find(v)) puts("zero"); else if(tmp == -1) puts("one"); else if(num[tmp] == 1) puts("one"); else puts("two or more"); } } return 0;}