백준[9372] 상근이의 여행

문제 설명

풀이 방법

spanning tree의 간선의 개수를 구하는 간단한 dfs 문제다. 

spanning tree의 간선의 개수는 dfs 또는 bfs 탐색 중 사용하는 간선을 모으면 된다.

 

코드

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

bool visited[1003];
vector<vector<int>> v;
int ans;

void dfs(int s) {
    visited[s] = true;
    ans++;
    for (auto i : v[s]) {
        if (!visited[i]) dfs(i);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, M; scanf("%d %d", &N, &M);
        v.clear(); v.resize(N + 1);
        memset(visited, false, sizeof(visited));
        while (M--) {
            int s, e; scanf("%d %d", &s, &e);
            v[s].push_back(e); v[e].push_back(s);
        }
        ans = 0;
        dfs(1);
        printf("%d\n", ans - 1); // ans은 노드의 개수이기 때문에 ans-1
    }
}C++

문제 링크 : acmicpc.net/problem/9372