小白求助BFS, 计算距离

要求只能更改红字部分, 不能用visited
红字部分是我的想法, 但是结果不对
应该怎么修改才能得到正确答案?
非常感谢!

1. 
   
2. #include <iostream>
   
3. #include <string>
   
4. 
   
5. // Note: You must not change the definition of DisjointSets here.
   
6. class DisjointSets {
   
7. public:
   
8.   int s[256];
   
9.   int distance[256];
   
10. 
    
11.   DisjointSets() {
    
12.     for (int i = 0; i < 256; i++) s[i] = distance[i] = -1;
    
13.   }
    
14. 
    
15.   int find(int i) { return s[i] < 0 ? i : find(s[i]); }
    
16.   
    
17.   void dsunion(int i, int j) {
    
18.     int root_i = find(i);
    
19.     int root_j = find(j);
    
20.     if (root_i != root_j) {
    
21.       s[root_i] = root_j;
    
22.     }
    
23.   }
    
24.   
    
25.   void bfs(int i, int n, int m, int edges[][2]);
    
26. };
    
27. 
    
28. 
    
29. /* Below are two conditions that need to be programmed
    
30. * to allow this procedure to perform a breadth first
    
31. * traversal and mark the edge distance of the graph's
    
32. * vertices from vertex i.
    
33. */
    
34. 
    
35. void DisjointSets::bfs(int i, int n, int m, int edges[][2]) {
    
36.   
    
37.   distance[i] = 0;
    
38. 
    
39.   // no need to iterate more than m times
    
40.   // but loop terminates when no new
    
41.   // vertices added to the frontier.
    
42.   
    
43.   for (int d = 1; d < m; d++) {
    
44.    
    
45.     // f is the index of the first
    
46.     // vertex added to the frontier
    
47.     int f = -1;
    
48. 
    
49.     // rooti is the name of the set
    
50.     // holding all of the vertices
    
51.     // that have already been assigned
    
52.     // distances
    
53.    
    
54.     int rooti = find(i);
    
55. 
    
56.     // loop through all of the edges
    
57.     // (this could be much more efficient
    
58.     // if an adjacency list was used
    
59.     // instead of a simple edge list)
    
60.    
    
61.     for (int j = 0; j < m; j++) {
    
62. 
    
63.       // root0 and root1 are the names of
    
64.       // the sets that the edge's two
    
65.       // vertices belong to
    
66. 
    
67.       int root0 = find(edges[j][0]);
    
68.       int root1 = find(edges[j][1]);
    
69.       
    
70. 
    
71.       if ( [color=#ff0000]root1 != rooti[/color] ) {
    
72. 
    
73.         // add the [1] vertex of the edge
    
74.         // to the frontier, either by
    
75.         // setting f to that vertex if it
    
76.         // is the first frontier vertex
    
77.         // found so far, or by unioning
    
78.         // it with the f vertex that was
    
79.         // already found.
    
80.         
    
81.         if (f == -1)
    
82.           f = edges[j][1];
    
83.         else
    
84.           dsunion(f,edges[j][1]);
    
85. 
    
86.         // set the distance of this frontier
    
87.         // vertex to d
    
88. 
    
89.         distance[edges[j][1]] = d;
    
90.         
    
91.       } else if ( [color=#ff0000]root0 != rooti[/color] ) {
    
92.         if (f == -1)
    
93.           f = edges[j][0];
    
94.         else
    
95.           dsunion(f,edges[j][0]);
    
96.         distance[edges[j][0]] = d;
    
97.       }
    
98.     }
    
99.    
    
100.     // if no vertices added to the frontier
     
101.     // then we have run out of vertices and
     
102.     // are done, otherwise union the frontier
     
103.     // set with the set of vertices that have
     
104.     // already been processed.
     
105.    
     
106.     if (f == -1)
     
107.       break;
     
108.     else
     
109.       dsunion(f,i);
     
110.   }
     
111. }
     
112. 
     
113. int main() {
     
114. 
     
115.   int edges[8][2] = {{0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,3}};  
     
116. 
     
117.   DisjointSets d;
     
118. 
     
119.   d.bfs(3,8,8,edges);
     
120. 
     
121.   for (int i = 0; i < 8; i++)
     
122.     std::cout << "Distance to vertex " << i
     
123.               << " is " << d.distance[i] << std::endl;
     
124. 
     
125. // Should print
     
126. // Distance to vertex 0 is 3
     
127. // Distance to vertex 1 is 2
     
128. // Distance to vertex 2 is 1
     
129. // Distance to vertex 3 is 0
     
130. // Distance to vertex 4 is 1
     
131. // Distance to vertex 5 is 2
     
132. // Distance to vertex 6 is 2
     
133. // Distance to vertex 7 is 1
     
134. 
     
135. 
     
136.   return 0;
     
137. }

复制代码

[/i][/i][/i][/i][/i][/i]

没看到有红字部分啊。而且不是很清楚你的m和n的定义，这感觉就是在并查集里面运行bfs.如果我理解是对的话，就是需要填if和else if的判断条件。
第一个if的地方填 root0 == rooti && root1 != rooti, 第二个 else if那里填root1 == rooti && root0 != rooti

思考过程是这样的，root0 == rooti的话，说明这条边的edge[0]已经被访问过了，那么另一个点到你的source的距离自然就是+1了。你对d进行循环，就实现了这个功能。
逻辑就是所有访问过的点，都会union起来，root都会变成你的起点i。所以只要看一下root是不是你的起点，就知道当前节点有没有被访问过了。

Python写这个就20行代码。你这100多行，建议刷题还是早转Python吧，磨刀不误砍柴工。

tinlittle 发表于 2020-5-30 12:35
Python写这个就20行代码。你这100多行，建议刷题还是早转Python吧，磨刀不误砍柴工。

也没那么大差距啊，除掉注释也就是三四十行。写一个并查集本身确实就需要一些代码量了。