登錄—專業IT筆試面試備考平臺_牛客網

題目大意：有一個n個點的圖，有一個人從s要走到t，在每走一步之前要刪除當前點的一個鄰邊，問能否到達t點

思路：我們不妨從后向前推，如果有一條邊能到終點，那么這個點如果到終點必須至少有兩條路，那么這樣的點就被成為勝利點，如果要在上一層再找到這樣的勝利點，就需要下次的點至少有兩條邊連接上層的某個點，所以只需要從終點開始bfs遍歷所有勝利點，同時用隊列維護所有上一層的勝利點

#include<bits/stdc++.h> using namespace std; const int N = 105, mod = 998244353; int b[N], cnt[N]; vector<int>g[N]; bool vis[N]; int n, m, s, t; bool flag = 0; void bfs() {queue<int>q;q.push(t); while (!q.empty()){int u = q.front();q.pop();vis[u] = 1;if (u == s)//成功到了起點{flag = 1;return;}for (int i = 0; i < g[u].size(); i++){int v = g[u][i];if (!vis[v] ){cnt[v]++;//給上一層的點的計數+1if(cnt[v]==2)q.push(v);//如果計數大于等于2，就把下個點放入隊列}}}} int main() {int tt;cin >> tt;while (tt--){flag = 0;scanf("%d%d%d%d", &n, &m, &s, &t);for (int i = 1; i <= m; i++){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);//鄰接表存圖}bfs();if (!flag){printf("Cut Player\n");}else{printf("Join Player\n");}for (int i = 1; i<= n; i++){g[i].clear();vis[i] = 0;cnt[i] = 0;}}return 0; }

總結

以上是生活随笔為你收集整理的Shannon Switching Game?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。