这题是个dfs,完全没有想到,我脑子里闪过离散数学的着色问题,然后止步于此,不过没关系,还有ai不得不说,这个好简洁啊!!
好的,这题对我来说收获还挺多的,边界错误已经说不完了,对小知识点上,我觉得我知道了bool只能全部初始化为false,true是不行的,第一遍带着代码敲问题依旧很多,在不少地方漏了这个变量,写错了那个变量,只能说我的问题还是很大的比起以前遇到的的dfs题目,这次的算简单,count用来计算当前状态的有几个完全独立的dfs则是负责将所有有关系的找出来
现在的我连算法都判断不出来,,,,,这次做题过程主要是,看题目,不会,感觉像着色问题,但是不是很会下手,总共也就是看了个题目,然后ai看到ai思考过程中有并查集,发现确实好像,最后还是看的dfs,然后开始想看代码理解,,,,好困,,,,,,,,,(~_~)就开始将变量打出来,在前面输入输出打出来,然后看count函数,发现懂了,dfs也就更容易理解了,但是虽然是看ai但没有照抄,出来了一大堆问题,总的来说解决完发现,整体过了4,5遍才过,觉得再打一遍,不看参考,然后就好啦!!!
#include <iostream> #include <bits/stdc++.h> using namespace std; int n, m, k; int vis[505] = {false}; int capture[505] = {false}; vector <int>g[505]; void dfs(int i) { vis[i] = true; for (int v : g[i]) { if (!vis[v] == true && !capture[v] == true) { dfs(v); } } } int count() { for (int i = 0; i < n; i++) { vis[i] = false; } int cnt = 0; for (int i = 0; i < n; i++) { if (!capture[i] == true && !vis[i] == true) { cnt++; dfs(i); } } return cnt; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } cin >> k; vector<int>attack; for (int i = 0; i < k; i++) { int c; cin >> c; attack.push_back(c); } int c = count(); for (int i : attack) { capture[i] = true; int cc = count(); if (cc > c) { printf("Red Alert: City %d is lost!", i); } else { printf("City %d is lost.", i); } c = cc; cout << endl; if (cc == 0) { cout << "Game Over."; } } }
