HDU 3749 Financial Crisis（双连通分量）

本题考察的是无向图的点双连通分量

Financial Crisis（HDU3749）

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1000 Accepted Submission(s): 325

Problem Description
Because of the financial crisis, a large number of enterprises go bankrupt. In addition to this, other enterprises, which have trade relation with the bankrup enterprises, are also faced with closing down. Owing to the market collapse, profit decline and funding chain intense, the debt-ridden entrepreneurs
have to turn to the enterprise with stably developing for help.

Nowadays, there exist a complex net of financial trade relationship between enterprises. So if one of enterprises on the same financial chain is faced with bankrupt, leading to cashflow’s obstruction, the other enterprises related with it will be influenced as well. At the moment, the foresight entrepreneurs are expected the safer cooperation between enterprises. In this sense, they want to know how many financial chains between some pairs of enterprises are independent with each other. The indepence is defined that if there exist two roads which are made up of enterprises(Vertexs) and their financial trade relations(Edge) has the common start point S and end point T, and expect S and T, none of other enterprise in two chains is included in these two roads at the same time. So that if one of enterpirse bankrupt in one of road, the other will not be obstructed.

Now there are N enterprises, and have M pair of financial trade relations between them, the relations are Mutual. They need to ask about Q pairs of enterprises’ safety situations. When two enterprises have two or more independent financial chains, we say they are safe enough, you needn’t provide exact answers.

Input
The Input consists of multiple test cases. The first line of each test case contains three integers, N ( 3 <= N <= 5000 ), M ( 0 <= M <= 10000 ) and Q ( 1 <= Q <= 1000 ). which are the number of enterprises, the number of the financial trade relations and the number of queries.
The next M lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means enterpirse u and enterprise v have trade relations, you can assume that the input will not has parallel edge.
The next Q lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means entrepreneurs will ask you the financial safety of enterpirse u and enterprise v.
The last test case is followed by three zeros on a single line, which means the end of the input.

Output
For each case, output the test case number formated as sample output. Then for each query, output “zero” if there is no independent financial chains between those two enterprises, output “one” if there is only one such chains, or output “two or more”.

Sample Input
3 1 2
0 1
0 2
1 0
4 4 2
0 1
0 2
1 2
2 3
1 2
1 3
0 0 0

Sample Output
Case 1:
zero
one
Case 2:
two or more
one

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20100;
int n,m,q;
int ecnt,ji,hea,cntt;
struct Edge{
    int next,to;
}edge[MAXN*2];
int F[MAXN],head[MAXN],DFN[MAXN],low[MAXN];
void add(int u,int v){
    edge[ecnt].to = v;
    edge[ecnt].next = head[u];
    head[u] = ecnt++;
}
struct Node{
    int u,v;
}stk[MAXN];
vector<int>v[MAXN];
int sz[MAXN];
void init(){
    ecnt = 1;
    ji = hea = cntt= 0;
    for(int i = 0; i <=n+10; i++){
        F[i] = i;
        head[i] = low[i] = sz[i] = 0;
        DFN[i] = -1;
        v[i].clear();
    }
    memset(edge,0,sizeof(edge));

}
int find(int x){
    if(x == F[x])return x;
    return F[x] = find(F[x]);
}

void tarjan(int x,int f){
    DFN[x] = low[x] = ++ji;
    for(int i = head[x]; i; i = edge[i].next){
        int to = edge[i].to;
        if(to != f){
            Node e;
            e.u = x; e.v = to;
            if(DFN[to] == -1){
                stk[++hea] = e;
                tarjan(to,x);
                low[x] = min(low[x],low[to]);
                if(low[to] >= DFN[x]){//找到割点
                    Node temp;
                    set<int> s;
                    cntt++;//记录点双分量的个数，标记点
                    while(1){
                        temp = stk[hea--];
                        s.insert(temp.u);
                        s.insert(temp.v);
                        v[cntt].push_back(temp.u);
                        v[cntt].push_back(temp.v);
                        if(temp.u == x && temp.v == to)break;
                    }
                    sz[cntt] = s.size();
                }
            }
            else{
                if(DFN[to] < DFN[x])stk[++hea] = e;
                low[x] = min(low[x],DFN[to]);
            }
        }
    }
}
int check(int x,int y){
    int flagx,flagy;
    for(int i = 1; i <= cntt; i++){
        flagx = flagy = 0;
        for(int j = 0; j < v[i].size(); j++){
            if(v[i][j] == x){
                if(flagy == 1){
                    if(sz[i] > 2)return 1;
                    else return 0;//当输入的图是两点一线时，为特殊情况，应输出one
                }
                else flagx = 1;
            }
            if(v[i][j] == y){
                if(flagx == 1){
                    if(sz[i] > 2)return 1;
                    else return 0;
                }
                else flagy = 1;
            }
        }
    }
    return 0;
}
int main(){
    int T = 0;
    while(~scanf("%d %d %d",&n,&m,&q)){
        if(n == 0 && m == 0 && q == 0)break;
        init();
        for(int i = 1; i <= m; i++){
            int x,y;
            scanf("%d %d",&x,&y);
            x++;y++;
            add(x,y);add(y,x);
            int fx = find(x);
            int fy = find(y);
            if(fx != fy) F[fx] = fy;
        }
        for(int i = 1; i <= n; i++){
            if(DFN[i] == -1){
                tarjan(i,0);
            }
        }
        printf("Case %d:\n",++T);
        for(int i = 1; i <= q; i++){
            int x,y;
            scanf("%d %d",&x,&y);
            x++;y++;
            int fx = find(x),fy = find(y);
            if(fx != fy){
                printf("zero\n");
                continue;
            }
            if(check(x,y))printf("two or more\n");
            else printf("one\n");
        }
    }
    return 0;
}
  

 

  
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
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/79335862