[백준 17352] 여러분의 다리가 되어 드리겠습니다! (C++)

문제 링크: https://www.acmicpc.net/problem/17352

17352번: 여러분의 다리가 되어 드리겠습니다!

1. 주의할 점

- 딱히 없다

- 입력이 많을 수 있기 때문에 입출력 속도에 신경쓴다

 

2. 구현

- 벡터 V[]를 사용하여 모든 간선을 저장한다(양방향)

- Flag[] 배열을 사용하여 0에 속하는 마을과 1에 속하는 마을로 나눈다

- 1에서 도달할 수 있는 모든 마을의 Flag[]에 1을 저장한다

- 처음에 무조건 1을 출력해도 상관없기 때문에 처음은 1로 고정하고, Flag[]값 중에서 0인 부분 아무거나 1개 Idx에 저장 후 출력한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[300001];
int flag[300001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, s, e, idx = 0;
	cin >> node;
	for (int i = 0; i < node - 2; i++) {
		cin >> s >> e;
		v[s].push_back(e);
		v[e].push_back(s);
	}
	queue<int> q;
	q.push(1);
	flag[1] = 1;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (flag[next] == 0) {
				flag[next] = 1;
				q.push(next);
			}
		}
	}
	for (int i = 1; i <= node; i++) {
		if (flag[i] == 0) {
			idx = i;
			break;
		}
	}
	cout << 1 << " " << idx;
	system("pause");
	return 0;
}