发现环

原创

问题描述

　　小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
　　不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
　　为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？

输入格式

　　第一行包含一个整数N。
　　以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。
　　对于30%的数据，1 <= N <= 1000
　　对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N
　　输入保证合法。

输出格式

　　按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。

样例输入

5
1 2
3 1
2 4
2 5
5 3

样例输出

1 2 3 5

　　思路：并查集+DFS，在读入边的同时判断边的两个结点是否属于同一个集合，若属于同一个集合则说明这两个结点

是环上的两个结点（很好理解，可以自己画图试试），将这两个结点作为起点和终点，从起点开始深搜，到终点的路径

上的所有结点就是环上的结点。

　　题目很好理解，在图中找一个环（有且只有一个），之前直接用暴力深搜解答过，放到官网运行超时。

超时的原因有两个：

　　一：之前我没有用合理的数据结构存储图，直接用了数组来存储边，然后每次搜索都要搜索整张图，很浪费时间，

今天刚学习到可以用vector存储图（其实就像是二维矩阵一样），每个结点都拥有一个属于自己的容器，容器里面存储

着与其直接相连的结点。

　　二：没有使用并查集，不知道哪个结点在环上，只能一个一个结点的去试。

　　有点纳闷，用C++写可以AC，用JAVA写没有用vector超时！

C++

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn=100005;
 6 
 7 int N;
 8 int qi_Dian;    //深搜起点 
 9 int zhong_Dian;    //深搜终点 
10 int father[maxn];    //存储每个结点的父结点  
11 int way[maxn];    //存储路径
12 int book[maxn];    //访问与否 
13 int total;    //存储环上结点总数 
14 int flag=0;
15 vector<int> matrix[maxn];    //二维容器vector 
16 
17 //寻找父结点 
18 int find_Father(int spot){
19     return spot==father[spot]?spot:father[spot]=find_Father( father[spot] );
20 }
21 
22 void dfs(int spot,int count){    //spot代表结点,count代表way[count] 
23     if(spot==zhong_Dian){
24         flag=1;
25         total=count-1;
26         return;
27     }
28     for(int i=0;i<matrix[spot].size();i++){
29         int v=matrix[spot][i];
30         if(book[v]==0){
31             book[v]=1;
32             way[count]=v;
33             dfs(v,count+1);
34             if(flag==1){
35                 return;
36             }
37             book[v]=0;
38         }
39     }
40 }
41 
42 int main(){
43     scanf("%d",&N);
44     //并查集初始化
45     for(int i=1;i<=N;i++){
46         father[i]=i;
47     }
48     //读入边
49     for(int i=1;i<=N;i++){
50         int one;    //第一条边 
51         int two;    //第二条边 
52         scanf("%d%d",&one,&two);
53         int one_Father=find_Father(one);
54         int two_Father=find_Father(two);
55         //判断头结点是否相等,相等则赋值为起点终点 
56         if(one_Father==two_Father){
57             qi_Dian=one;
58             zhong_Dian=two;
59         }
60         else{    //不相等则并合并 
61             father[two_Father]=one_Father;
62             //压入容器,相当于二维邻接矩阵 
63             matrix[one].push_back(two);
64             matrix[two].push_back(one);
65         } 
66     } 
67     //开始深搜
68     book[qi_Dian]=1;
69     way[1]=qi_Dian;
70     dfs(qi_Dian,2);
71     sort(way,way+total+1);
72     for(int i=1;i<=total;i++){
73         printf("%d ",way[i]);
74     }
75     return 0;
76 }

JAVA

 1 import java.util.*;
 2 import java.util.Arrays;
 3 
 4 public class Main {
 5     
 6     static int N;
 7     static int matrix[][];    //邻接矩阵
 8     static int book[][];    //标记边是否遍历
 9     static int father[];
10     static int qi_Dian;    //起点
11     static int zhong_Dian;    //终点
12     static int way[];    //存储路径
13     static int flag=0;
14     static int total;
15 
16     //寻找父结点
17     static int find_Father(int spot) {
18         if(spot!=father[spot]) {
19             return father[spot]=find_Father( father[spot] );
20         }
21         return spot;
22     }
23     
24     static void dfs(int spot,int count) {    //点spot,count为路径数组索引
25         //终点判断
26         if(spot==zhong_Dian) {
27             total=count-1;
28             flag=1;
29             return;
30         }
31         for(int i=1;i<=N;i++) {
32             //起点和终点不能直接相连
33             if(spot==qi_Dian && i==zhong_Dian) {
34                 continue;
35             }
36             if(matrix[spot][i]==1 && book[spot][i]==0) {
37                 book[spot][i]=1;
38                 book[i][spot]=1;
39                 way[count]=i;
40                 dfs(i,count+1);
41                 if(flag==1) {
42                     return;
43                 }
44                 book[spot][i]=0;
45                 book[i][spot]=0;
46             }
47         }
48     }
49 
50     public static void main(String[] args) {
51         Scanner reader=new Scanner(System.in);
52         N=reader.nextInt();
53         matrix=new int[N+1][N+1];
54         father=new int[N+1];
55         book=new int[N+1][N+1];
56         way=new int[N+1];    //最多有N个结点
57         //结点指向本身(并查集初始化)
58         for(int i=1;i<=N;i++) {
59             father[i]=i;
60         }
61         //读入边
62         for(int i=1;i<=N;i++) {
63             int one=reader.nextInt();
64             int two=reader.nextInt();
65             matrix[one][two]=1;
66             matrix[two][one]=1;
67             //寻找这两个结点的父结点
68             int one_Father=find_Father(one);
69             int two_Father=find_Father(two);
70             //判断两个头结点是否相等,不相等合并
71             if(one_Father!=two_Father) {
72                 father[two_Father]=one_Father;
73             }
74             //相等,赋值为深搜的起点和终点
75             else if(one_Father==two_Father) {
76                 qi_Dian=one;
77                 zhong_Dian=two;
78             }
79         }
80         way[1]=qi_Dian;
81         dfs(qi_Dian,2);    //从起点开始深搜,找到终点结束
82         Arrays.sort(way,0,total+1);
83         for(int i=1;i<=total;i++) {
84             System.out.print(way[i]+" ");
85         }
86     }
87 
88 }

14:34:40

2018-08-14