MYF

HDU 3749 Financial Crisis

Posted on | In | | Visitors

题目链接

HDU 3749

解题方法：点连通分量，计算两点间点路径数量

题目分析

题目大意

给你一个(保证输入无重边,无自环)无向图,然后有下面Q条询问,每条询问为:问你u点与v点之间有几条(除了首尾两点外,其他点不重复)的路径.如果有0条或1条输出zero或one,如果有2条以上,输出”two or more”.

解析

Tarjan统计点连通分量的模版题，比较坑的是需要判断所在的点连通分量的元素个数，如果元素个数小于等于2时只有一条路径

详解HDU 3749 Financial Crisis(点-双连通分量)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-11;
//点-双连通分量
const int maxn=5000+10;//点数
struct Edge{
    int u,v;
    Edge(int _u,int _v){
        u = _u, v = _v;
    }
};
int pre[maxn]; //第一次访问的dfs_clock时间戳
int low[maxn];
int vis[maxn];
int tt;
int iscut[maxn]; //割点判断
int bccno[maxn]; // bccno[i]表示i所在的点-双联通分量的下标 即bcc[bccno[i]]这个连通分量集合中含有i这个点 对于割顶来讲没有意义，因为他属于多个点-双联通分量
vector<int>belong[maxn];
int dfs_clock;
int bcc_cnt; // 双连通分量个数
vector<int>G[maxn]; // 顶点，下标0~n-1
vector<int>bcc[maxn]; //点双连通分量存储结果 下标1~bcnt
stack<Edge>S;
int dfs(int u,int fa){
    vis[u] = tt;
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for (int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        Edge e = Edge(u, v);
        if (!pre[v]) {
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= pre[u]) {
                iscut[u] = true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                while (true) {
                    Edge x = S.top();
                    S.pop();
                    if (bccno[x.u]!=bcc_cnt) {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u] = bcc_cnt;
                        belong[x.u].push_back(bcc_cnt);
                    }
                    if (bccno[x.v] != bcc_cnt) {
                        bcc[bcc_cnt].push_back(x.v);
                        belong[x.v].push_back(bcc_cnt);
                    }
                    if (x.u == u && x.v ==v) {
                        break;
                    }
                }
            }
            
        }
        else if(pre[v] < pre[u] && v != fa){
            S.push(e);
            lowu = min(lowu, pre[v]);
        }
    }
    if (fa < 0 && child == 1) {
        iscut[u] = 0;
    }
    return  low[u]=lowu;
}
int find_bcc(int n){//n个顶点
    //栈无需清空，每次跑完必然为空
    //bcc[]无需清空，组建连通分量时已清空
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    memset(low, 0, sizeof(low));
    memset(vis, -1, sizeof(vis));
    dfs_clock = bcc_cnt = 0;
    int cnt = 0;
    for (int i=0; i<n; i++) {
        if (!pre[i]) {
            tt = i;
            dfs(i, -1);
            cnt++;
        }
    }
    return cnt;
}

void work(int n,int m, int q){// n个点 m条边
    // input and initialize
    for (int i=0; i<n; i++) {
        G[i].clear();
        belong[i].clear();
    }
    for (int i=0; i<m; i++) {
        int u,v;
        scanf("%d%d",&u,&v);//index range: 0~n-1
        //        u--,v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    // find biconnected component
    int cnt = find_bcc(n);
    
    // output
    for (int i=0; i<q; i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        if (vis[u]!=vis[v]) {
            cout<<"zero\n";
        }
        else if (bccno[u]!=bccno[v]){
            bool flag =false;
            for (int i=0; i<belong[u].size()&&!flag; i++) {
                for (int j=0; j<belong[v].size()&&!flag; j++) {
                    if (belong[u][i] == belong[v][j]) {
                        int tmp = belong[u][i];
                        if (bcc[tmp].size()>2) {
                            flag = true;
                        }
                    }
                }
            }
            if (!flag)
                cout<<"one\n";
            else
                cout<<"two or more\n";
        }
        else{
            if (bcc[bccno[u]].size()<=2)
                cout<<"one\n";
            else
                cout<<"two or more\n";
        }
    }
}
int main(){
    int n,m,q,cas=0; //n个点 m条边
    while (scanf("%d%d%d",&n,&m,&q),n) {
        printf("Case %d:\n",++cas);
        work(n, m, q);
    }
}