첫번째 시도
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T, N, M;
int a, b;
bool visited[1001];
int ans;
void bfs(int start,vector<int> v[1001]) {
for (int i = 0; i < 1001; i++) {
visited[i] = false;
}
ans = 0;
queue<int>q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node=q.front();
q.pop();
for (int i = 0; i < v[node].size(); i++) {
int next = v[node][i];
if (!visited[next]) {
q.push(next);
visited[next] = true;
ans++;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
vector<int> v[1001];
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
bfs(1,v);
cout << ans<<'\n';
}
return 0;
}BFS를 이용하여 모든 노드의 간선 개수를 세어주었다.
but 문제를 보면 비행스케줄은 항상 연결그래프를 이루기 때문에 노드를 잇는 간선의 개수를 구하는 문제랑 똑같은 문제이다.
N개의 노드에는 N-1개의 간선이 존재한다
위의 정의로 풀면 더 간단하게 풀리는 문제이다.
두번째 시도
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T, N, M;
int a, b;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> a >> b;
}
cout << N - 1<<'\n';
}
return 0;
}