#UVa:280-Vertex

灆洢 2018-10-10 01:41:57

利用 DFS 遍歷整個圖即可。

P.S. 起始點在剛開始不算可以到的了的點,除非在遍歷中能夠經過它才算數。

C++(0.090)

/*******************************************************/
/* UVa 280 Vertex                                      */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/10                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int dfs(const vector<vector<int>> &edges, vector<int> &isVisited, int startVertex){ 
  int visitVertexCount = 0;
  for(int i = 0 ; i < edges[startVertex].size() ; ++i){
    int endVertex = edges[startVertex][i];
    if(!isVisited[endVertex]){
      isVisited[endVertex] = true;
      ++visitVertexCount;
      visitVertexCount += dfs(edges, isVisited, endVertex);
    }
  }
  return visitVertexCount;
}

int main(){
  int n;
  while(scanf("%d", &n) != EOF && n != 0){
    vector<vector<int>> edges(n+1);
    int edgeStartVertex;
    while(scanf("%d", &edgeStartVertex) != EOF && edgeStartVertex != 0){
      int edgeEndVertex;
      while(scanf("%d", &edgeEndVertex) != EOF && edgeEndVertex != 0){
        edges[edgeStartVertex].push_back(edgeEndVertex);
      }
    }

    int startVertexCount;
    scanf("%d", &startVertexCount);
    for(int i = 0 ; i < startVertexCount ; ++i){
      int startVertex;
      scanf("%d", &startVertex);
      vector<int> isVisited(n+1, false);
      int inaccessibleVertexCount = n - dfs(edges, isVisited, startVertex);

      printf("%d", inaccessibleVertexCount);
      for(int i = 1 ; i <= n ; ++i){
        if(!isVisited[i]) printf(" %d", i);
      }
      printf("\n");
    }
  }
  return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料