[9372] 상근이의 여행​, c++

[9372] 상근이의 여행

​

 

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

한줄 후기 : 상근씨는 누굴까?

 

 

보자마자 아 그냥 모든 정점 bfs 돌면서 개수 센 후 최소 출력하면 되겠다 라고 생각했다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, cnt=0;
vector<int> air[1001];	
void bfs(int start){
	queue<int> q;
	int visit[1001] = {0};
	q.push(start);
	visit[start] = 1;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i=0; i<air[x].size(); i++){
			int y = air[x][i];
			if(!visit[y]){
				q.push(y);
				visit[y] = 1;
				cnt++;
			}
		}
	}
}
int main(){
	int t, a,b, max_cnt=10000000;
	cin >> t;
	while(t--){
		scanf("%d %d", &n, &m);
		for(int i=0; i<m; i++){
			scanf("%d %d",&a,&b);
			air[a].push_back(b);
			air[b].push_back(a);
		}
		for(int i=1; i<=n; i++){
			bfs(i);
			max_cnt=min(cnt, max_cnt);
		}
		for(int i=1; i<=n; i++){
			air[i].clear();
		}
		printf("%d\n", max_cnt);
		max_cnt=10000000;	cnt=0;
	}
	return 0;
}

왕복 하는 비행기 이므로 벡터 연결리스트에 반대로도 넣어줘야 함.

그리고 이 문제는 어이없는게 그냥 정점-1 즉, 간선의 수가 답일 수 밖에 없음 ㅋㅋㅋㅋ

​

무튼 우리 셋 다 연구소 풀고 멘탈 나가서 상근이의 여행만 풀고 술 마시러 갔다.

 

이거 풀땐 코로나 없었다. 슬프다.