[伯俊]9372号尚根の旅

質問リンク:https://www.acmicpc.net/problem/9372

質問する

冬休みを迎えるため、尚根はNカ国を旅行し、自分を探すことにした.
しかし、尚根は新しい飛行機が怖いので、最小限の飛行機で国に行きたいと思っています.
今度の休みの飛行スケジュールができたとき、尚勤が一番少ない飛行機ですべての国を旅行するのを手伝った.
尚勤が一つの国から別の国に移ったとき、別の国(すでに訪問した国)を通っても.

入力

1行目は、テストケースの数T(T≦100)である.
各テストケースでは、次の情報が提供されます.

第1列は、国の数N(2≦N≦1000)および飛行機の種類M(1≦M≦10000)を与える.

の後、M行にaとbのペアを入力します.aとbを往復する飛行機があることを意味する.(1 ≤ a, b ≤ n; a ≠ b)

によって与えられる飛行行程は、常に接続図を形成する.

しゅつりょく

テストボックスごとに1行出力します.

上根は、すべての国を旅行するために乗る飛行機の種類の最小数を出力します.

質問へのアクセス

これは木理論の問題です.
入力するとグラフが表示されます.与えられた図形で木を求め,木のedge個数を求めればよい.ツリーは常にループが存在しないためedgeの個数はnode-1に固定される.
したがって,入力したノード数から1を減算すると,答えが得られる.

コード実装（C++）

#include <iostream>

using namespace std;

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

    int testcase;
    cin >> testcase;
    int N, M, n, m;
    for(int i = 0 ; i < testcase ; i++){
        cin >> N >> M;
        for(int j = 0 ; j < M; j++){
            cin >> n >> m;
        }
        cout << N-1 << "\n";
    }
}