[演算法心得] Codeforces. Valid BFS?

jimmyhealer

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

(昨天太忙了~~ 斷更QQ)

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: Valid BFS?
題目網站: Codeforces
題目網址: https://codeforces.com/problemset/problem/1037/D
題目內容:

The BFS algorithm is defined as follows.

Consider an undirected graph with vertices numbered from 1 to n. Initialize q as a new queue containing only vertex 1, mark the vertex 1 as used.
Extract a vertex v from the head of the queue q.
Print the index of vertex v.
Iterate in arbitrary order through all such vertices u that u is a neighbor of v and is not marked yet as used. Mark the vertex u as used and insert it into the tail of the queue q.
If the queue is not empty, continue from step 2.
Otherwise finish.
Since the order of choosing neighbors of each vertex can vary, it turns out that there may be multiple sequences which BFS can print.

In this problem you need to check whether a given sequence corresponds to some valid BFS traversal of the given tree starting from vertex 1. The tree is an undirected graph, such that there is exactly one simple path between any two vertices.

題目大意:

給你一張無向圖，並且給你一個BFS過程中遇到點的順序，問是否為合法順序。

範例輸入 #1:
4
1 2
1 3
2 4
1 2 3 4


範例輸出 #1:
Yes

範例輸入 #2:
4
1 2
1 3
2 4
1 3 2 4


範例輸出 #2:
Yes

--------------------------------------------------- 題解心得 ---------------------------------------------------

題目要求的是BFS順序，把紀錄過的順序讓他對於每一個子樹做排序。
另外一個重點是，為方便實作，可以用鄰接表而不是鄰接矩陣，因為如下。
假設 節點1 有三個子節點 分別為 節點2 節點3 節點 4，而BFS的順序為 1342。
代表 節點3 是第一個迭代的節點，節點4 為第二個迭代的節點, 等等...
那 節點1 的鄰接表排序後就變成 342。
最後只要正常的做BFS操作，每次紀錄加入佇列的點。
判斷是否個題目所給的順序相同即可。

AC code (811ms, 14992 KB):

1. #include<bits/stdc++.h>
   
2. #define ll long long
   
3. #define INF 0x3f3f3f3f
   
4. #define MOD 1000000007
   
5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
6. using namespace std;
   
7. const int MXN = 200005;
   
8. 
   
9. void sol(){
   
10.   ll ans = 0, n = 0, m = 0, k = 1;
    
11.   cin >> n;
    
12.   vector<vector<int> > path(n + 1);
    
13.   vector<int> ordered(n), index(n + 1);
    
14.   for(int i = 0; i < n - 1; ++i){
    
15.     int s, t;
    
16.     cin >> s >> t;
    
17.     path[s].emplace_back(t);
    
18.     path[t].emplace_back(s);
    
19.   }
    
20.   for(int i = 0; i < n; ++i){
    
21.     cin >> ordered[i];
    
22.     index[ordered[i]] = i;
    
23.   }
    
24.   for(int i = 1; i <= n; ++i){
    
25.     sort(path[i].begin(), path[i].end(), [&](int a, int b){
    
26.           return index[a] < index[b];
    
27.         });
    
28.   }
    
29.   queue<int> q;
    
30.   vector<int> vis(n + 1), res;
    
31.   q.push(1);
    
32.   while(!q.empty()){
    
33.     int p = q.front(); q.pop();
    
34.     vis[p] = 1;
    
35.     res.emplace_back(p);
    
36.     for(int i : path[p]){
    
37.       if(!vis[i]) q.push(i);
    
38.     }
    
39.   }
    
40.   for(int i = 0; i < n; ++i){
    
41.     if(ordered[i] != res[i]){
    
42.       cout << "No\n";
    
43.       return;
    
44.     }
    
45.   }
    
46.   cout << "Yes\n";
    
47. }
    
48. 
    
49. int main(){
    
50.   //io
    
51.   int t = 1;
    
52.   while(t--){
    
53.     sol();
    
54.   }
    
55. }
    

複製代碼