1013. Battle Over Cities 解析

这个题目其实是DFS遍历图，然后看要几遍才能遍历完整个图。然后那个城市被占领就是那个点已经访问过。还要几次才能遍历完。

#include <iostream>
#include <vector>

using namespace std;



void DFS(vector<int> * Ad,bool * isVisit, int u) {
 isVisit[u] = true;
 for (int i = 0; i < Ad[u].size(); i++) {
  int v = Ad[u][i];
  if (!isVisit[v])
   DFS(Ad,isVisit,v);
 }
}

int DFSTrave(vector<int> * Ad, bool * isVisit, int N) {
 int times = 0;
 for (int u = 0; u < N; u++) {
  if (!isVisit[u]) {
   DFS(Ad,isVisit,u);
   times++;
  }
 }
 return times - 1;
}


int main(){

 int N, M, K;
 cin >> N >> M >> K; //N顶点数 M边数 K监测点数

 vector<int> * Ad = new vector<int> [N];
 bool * isVisit = new bool[N];
 
 
 int tempHead =0 , tempTail = 0;
 for (int i = 0; i < M; i++) {
  cin >> tempHead >> tempTail; 
  tempHead = tempHead - 1; //归0 题目点从1开始
  tempTail = tempTail - 1;//归0
  Ad[tempHead].push_back(tempTail);
  Ad[tempTail].push_back(tempHead);
 }

 //for (int i = 0; i < N; i++) {
 // cout << i << ": ";
 //  for (int j = 0; j < Ad[i].size(); j++)
 //   cout << Ad[i][j] << " ";
 // cout << endl;
 //}

 vector <int> F;
 int tempF;
 for (int i = 0; i < K; i++) {
  cin >> tempF;
  tempF = tempF - 1;//归0
  F.push_back(tempF);
 }


 for (int i = 0; i < F.size(); i++){
  int Num = 0;
  for (int i = 0; i < N; i++)
   isVisit[i] = false;
  isVisit[F[i]] = true;
  Num = DFSTrave(Ad, isVisit, N);
  cout << Num << endl;
 }

}