admin管理员组文章数量:1558098
Financial Crisis
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1234 Accepted Submission(s): 391
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
Author
possessor WC
Source
HDU 3rd “Vegetable-Birds Cup” Programming Open Contest
Recommend
lcy
Statistic | Submit | Discuss | Note
算法分析:
题意:
给一个无向图, n <5000, m < 10000,保证输入无重边,无自环
Q条询问,每条询问为:问你u点与v点之间有几条(除了首尾两点外,其他点不重复)的路径条数. 只需回答有0条还是1条还是多条
分析:
分析:
根据题意,可以推出与点——双连通分量有关。
一个割点,可以属于多个点——双连通分量,如何求两点无重复点的路径呢?这里就要画图体会了,其实保证里面没有割点(即在u,v一个点—双两通分量),就可以保证uv之间有多于两条的路,当然有一种特殊情况,下面提到,这里直接给出结论(饶齐大佬的博客):
1.如果u点与v点不连通,直接输出0即可.(用并查集实现)
2.如果u点与v点属于同一个点-双连通分量,输出two or more.(这里有特例,两点一边的点-双连通分量应该输出1)
3. 剩下的所有情况表示u与v虽然连通,但是在不同的点-双连通分量类,直接输出1即可.
代码实现:
vector建树
https://blog.csdn/u013480600/article/details/31782327
结构体建树
https://blog.csdn/sdj222555/article/details/13746461
版权声明:本文标题:HDU 3749 Financial Crisis(点-双连通分量) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1727384478a1112268.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论