【并查集】ZOJ Problem Set – 3321 Circle

Circle

Time Limit: 1 Second      Memory Limit: 32768 KB


Your task is so easy. I will give you an undirected graph, and you just need to tell me whether the graph is just a circle. A cycle is three or more nodes V1V2V3, … Vk, such that there are edges between V1 and V2V2 and V3, … Vk and V1, with no other extra edges. The graph will not contain self-loop. Furthermore, there is at most one edge between two nodes.

继续阅读【并查集】ZOJ Problem Set – 3321 Circle

HDU P1232 畅通工程(并查集)

Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? 继续阅读HDU P1232 畅通工程(并查集)