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

[複製鏈接]

jimmyhealer

7 主題	0 好友	11 積分

新手上路

Rank: 1

UID: 320966
帖子: 146
主題: 7
精華: 0
積分: 11
楓幣: 756
威望: 11
存款: 0
贊助金額: 0
推廣: 0
ＧＰ: 31
閱讀權限: 10
性別: 保密
在線時間: 9 小時
註冊時間: 2021-9-30
最後登入: 2022-7-6

發消息

電梯直達

1樓

發表於 2022-5-10 14:32:34 |只看該作者 |倒序瀏覽

本帖最後由 jimmyhealer 於 2022-5-10 14:36 編輯

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 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):

#include<bits/stdc++.h>

#define ll long long

#define INF 0x3f3f3f3f

#define MOD 1000000007

#define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const int MXN = 200005;

void sol(){

  ll ans = 0, n = 0, m = 0, k = 1;

  cin >> n;

  vector<vector<int> > path(n + 1);

  vector<int> ordered(n), index(n + 1);

  for(int i = 0; i < n - 1; ++i){

int s, t;

cin >> s >> t;

path[s].emplace_back(t);

path[t].emplace_back(s);

  }

  for(int i = 0; i < n; ++i){

cin >> ordered[i];

index[ordered[i]] = i;

  }

  for(int i = 1; i <= n; ++i){

sort(path[i].begin(), path[i].end(), [&](int a, int b){

      return index[a] < index[b];

      });

  }

  queue<int> q;

  vector<int> vis(n + 1), res;

  q.push(1);

  while(!q.empty()){

int p = q.front(); q.pop();

vis[p] = 1;

res.emplace_back(p);

for(int i : path[p]){

   if(!vis[i]) q.push(i);

}

  }

  for(int i = 0; i < n; ++i){

if(ordered[i] != res[i]){

   cout << "No\n";

   return;

}

  }

  cout << "Yes\n";

}

int main(){

  //io

  int t = 1;

  while(t--){

sol();

  }

}

複製代碼