[伯俊/C+]17352号みんなの架け橋になる!

8888 ワード
17352 白駿 みんなの架け橋になる！ テキストリンク

[白俊]17352号大家的架桥!


1.質問


善隣の世界にはN個の島がある.島には1,2...、Nの番号が次から次へと.これらの島はN-1の橋につながっており、どの2つの島の間でも橋で往復することができます.
昨日まではそうでした.
「なぜN-1の橋しかないのか、通行しにくい」と、善隣世界に不満を抱いた旭済は橋を倒した!もともと不便だった通行がさらに不便になった.往復できない島ができたからです.政府は、まず善隣世界の建築家を雇用し、2つの異なる島を橋につなぎ、どの2つの島の間を往復するように緊急指示した.
でもあの建築家はあなたです!私は天下一コード大会に参加するのに忙しいです.

2.入力


最初の行は整数Nを与える.(2 ≤ N ≤ 300,000)
次のN-2ラインでは、旭済が倒壊していない橋を結ぶ2つの島の番号が与えられます.

3.出力


橋でこの2つの島の番号を印刷します.複数のメソッドがある場合は、いずれかのメソッドのみが出力されます.

4.解答

  • 分離セット問題
  • 親の異なる2つのノードを見つけ、2つのノードを出力すればよい.
  • Nと入力し、親を1からNに初期化します.
  • N−1ブリッジ情報を受信する.
  • 足をそろえます.
  • 親は別の2つのノードを見つけて印刷します.

    • 5.コード

    #include <iostream>
#include <algorithm>

using namespace std;

int n;
int parent[300001];

int findParent(int x) {
  if (parent[x] == x) return x;
  else return parent[x] = 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;

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

  for (int i = 0; i < n - 2; i++) {
    int a, b;
    cin >> a >> b;

    unionParent(a, b);
  }

  int a = -1;
  int b = -1;

  for (int i = 1; i <= n; i++) {
    if (a == -1) {
      a = findParent(i);
    }
    else {
      if (a != findParent(i)) {
        b = findParent(i);
        break;
      }
    }
  }
  cout << a << " " << b;
}
    [プログラマー]ユニホーム
    [JS]typeof演算子