[C++]旅行計画

10324 ワード
腎臓の木 cpp ps テキストリンク

1.質問


韓牛が暮らす国にはNの観光地があり、各観光地は1-N番の番号で区切られている.また、任意の2つの観光地の間に2つの観光地を結ぶ道路が存在する可能性がある.これは、観光地が道路につながっていれば、双方向に移動できることを意味します.旅行計画を立てた後、韓宇はこの旅行計画が実行できるかどうかを判断しようとした.例えば、N=5は、以下の道路情報が提供されていると仮定する.
  • 1号旅行地-2号旅行地
  • 1号旅行地-4号旅行地
  • 1号旅行地-5号旅行地
  • 2号旅行地-3号旅行地
  • 2号旅行地-4号旅行地

    • 2.入力

  • 第1行は、旅行地の数Nと、旅行計画に属する都市の数Mを与える.(1 ≤ N, M ≤ 500)
  • は、NX N行列によって、任意の2つの旅行先の間に接続があるかどうかを決定することができる.値が1の場合は相互に関連付けられています.値が0の場合は相互に関連付けられていないことを示します.
  • の最後の行には、韓宇旅行計画に含まれる旅行地の番号がスペースで区切られています.

    • 3.出力


    1行目の時に出来ればYES出力出来ればNO出力

    4.解答

  • 旅行計画に含まれている都市が相互に接続されているかどうかを確認すればよい.
  • 両親はすべて自分に初期化した.
  • 2=(같은 부모를 가지는지)配列を入力して相互に接続すると、N X N演算が行われる.
  • 旅行計画を入力して、都市の両親が同じかどうかを確認します.

    • 5.最初のコードで修正された点

  • 配列を格納する必要がないため,配列を削除した.

    • 6.ソース

    #include <iostream>
#include <vector>

using namespace std;

int n, m;
int parent[501];

int findParent(int x) {
  if(parent[x] == x) return x;
  else return findParent(parent[x]);
}

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

  if(a < b) parent[b] = a;
  else parent[a] = b;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin>>n>>m;

  for (int i = 0; i < n; i++) {
    parent[i] = i;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int x;
      cin>>x;
      
      if (x==1) {
        unionParent(i+1, j+1);
      }
    }
  }

  vector<int> plan;
  for (int i = 0; i < m; i++) {
    int x;
    cin>>x;
    plan.push_back(x);
  }

  bool answer = true;
  for (int i = 0; i < m-1; i++) {
    if (findParent(i) != findParent(i+1)) {
      answer = false;
      break;
    }
  }
  
  if (answer) cout<<"YES";
  else cout<<"NO";
}
    [JavaScript]テクノロジー選択:モジュール化とフレームワーク(二)
    html構造