Financial Crisis【点双连通分量】

题目链接 HDU - 3749

---

  你以为学了Tarjan会写几个边双就真的理解什么是双连通分量了吗？——我原来真的不懂什么叫做点双BCC。

  不过这都没有关系，解决了这个问题之后，我终于知道了什么叫做点双连通分量了。

  这是一个绝对绝对经典的问题，首先讲一下题意：

  给你一幅N个点，M条边的图（不一定连通），再给出Q个询问，每次的询问是u、v两点，从u到v是否有两条及以上“无重叠路径”，什么叫做“无重叠路径”呢？就是两条不同的路径上没有一个点是相同的（起点终点除外），此时输出two or more。如果两点不在一个连通图上，那么输出zero，剩下的就是输出one了。

  好了，那么我们首先来认识一下点双，什么叫做点双呢？

点双连通分量

  对于一个连通图，如果任意两点至少存在两条点不重复的路径，则称这个图为点双连通的。

点双连通分量的性质

1. 点双连通分量之间以割点连接，且两个点双连通分量之间有且只有一个割点；

2. 每一个割点可以任意属于多个点双连通分量，因此求点双连通分量时，可能包含重复的点；（求解本题将用到这条性质）

3. 只有一条边连通的两个点也是点双连通分量；（所以本题还需要判断点双分量中的点数是否大于2）

4. 对于此点为根的情况，第一个儿子也属于点双连通分量，故不能用判断割点的方式来判断，只要根据dfn[父]≤low[子]，便可将其加入点双；

5. 对于删去此点，不会不与祖辈连通的儿子，在处理其他儿子的点双连通分量时，不能将其删去。

  在本题中，主要利用的是2、3两条性质。

  剩下的，就是代码的构造了。

  给出一个比较强的样例：

8 10 2
0 1
0 2
1 2
1 3
1 5
3 4
4 5
4 6
4 7
6 7
1 4
0 1
ans:
two or more
two or more

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
#define MAX_3(a, b, c) max(a, max(b, c))
#define Rabc(x) x > 0 ? x : -x
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e4 + 7, maxM = 2e4 + 7;
int N, M, Q, head[maxN], cnt, root[maxN];
inline int fid(int x) { return x == root[x] ? x : root[x] = fid(root[x]); }
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxM];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
int dfn[maxN], tot, low[maxN], Stap[maxN], Stop, Bcnt, Bsiz[maxN];
vector<int> Belong[maxN];
void Tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++tot;
    Stap[++Stop] = u;
    for(int i=head[u], v, p; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa) continue;
        if(!dfn[v])
        {
            Tarjan(v, u);
            if(low[v] >= dfn[u])
            {
                Bcnt++; Bsiz[Bcnt] = 0;
                do
                {
                    p = Stap[Stop--];
                    Belong[p].push_back(Bcnt);
                    Bsiz[Bcnt] ++;
                } while(p ^ v);
                Belong[u].push_back(Bcnt);
                Bsiz[Bcnt]++;
            }
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
inline void init()
{
    cnt = tot = Stop = Bcnt = 0;
    for(int i=0; i<=N; i++)
    {
        head[i] = -1;
        root[i] = i;
        dfn[i] = 0;
        Belong[i].clear();
    }
}
int main()
{
    int Cas = 0;
    while(scanf("%d%d%d", &N, &M, &Q) && (N | M | Q))
    {
        init();
        for(int i=1, u, v, fu, fv; i<=M; i++)
        {
            scanf("%d%d", &u, &v); fu = fid(u); fv = fid(v);
            _add(u, v);
            if(fu ^ fv) root[fu] = fv;
        }
        for(int i=0; i<N; i++) if(!dfn[i]) Tarjan(i, -1);
        printf("Case %d:\n", ++Cas);
        int x, y, len_x, len_y;
        while(Q--)
        {
            scanf("%d%d", &x, &y);
            if(fid(x) ^ fid(y)) printf("zero\n");
            else
            {
                len_x = (int)Belong[x].size(); len_y = (int)Belong[y].size();
                bool ok = false;
                for(int i=0; i<len_x && !ok; i++)
                {
                    for(int j=0; j<len_y && !ok; j++)
                    {
                        if(Belong[x][i] == Belong[y][j] && Bsiz[Belong[x][i]] > 2)
                        {
                            ok = true;
                            printf("two or more\n");
                        }
                    }
                }
                if(!ok) printf("one\n");
            }
        }
    }
    return 0;
}