[백준][C++] 17414: Sebin Loves Euler Circuit

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

 

문제 제목이 '세빈은 오일러 회로를 좋아해'입니다.

오일러 회로 복습한김에 쉬운 오일러 회로, 트레일 문제좀 몇 개 풀어보려고 했는데 낚였습니다. 빡세네요.

 

일단 이 문제의 조건을 유심히 보셔야 합니다. 안그러면 저처럼 삽질하거든요

• 1. N개의 정점을 모두 방문해야 한다
• 2. [서브태스크 2]

 

일단 모든 정점을 방문해야 하니까 degree == 0인 노드도 연결해야 한다는 점을 명심하시고요

서브태스크 2가 좀 중요한데, 연결그래프가 아닌 그래프, 즉 여러 컴포넌트로 나뉜 그래프가 입력으로 주어질 수 있는 점을 고려해야 합니다.

 

서브태스크 1만 풀려면 그냥 홀수점 쭉 찾아서 두개씩 묶어서 출력하면 됩니다. (홀수점의 개수는 항상 짝수개입니다)

 

제 풀이방법은 이렇습니다.

• 그래프를 컴포넌트로 분리. 이때 컴포넌트의 홀수점과 짝수점을 분리
• 우선순위 큐를 만듦. 이때 각 컴포넌트의 홀수점의 개수가 우선순위가 되도록 만듦
  {컴포넌트의 홀수 점 개수, 컴포넌트의 인덱스}를 우선순위 큐에 넣음
• 컴포넌트가 하나가 될때까지 우선순위 큐에서 컴포넌트 두개를 빼서 하나로 합침
  • 컴포넌트 사이에 홀수점-홀수점, 홀수점-짝수점, 짝수점-짝수점 순의 우선순위로 1개의 간선을 추가
  • 큰 거에 작은거를 합쳐야 시간복잡도가 O(NlgN)가 된다고 함. 안그러면 O(N^2)
    아직 안배운 부분이라 증명은 못하겠네요;; -> 참고 링크
• 컴포넌트가 하나가 되면 남은 홀수점 두개씩 묶어서 출력

 

컴포넌트가 1개가 될 때까지 합치는게 핵심입니다.

대충 맞는 것 같은데 자꾸 시간 초과가 나길래 검색해봤더니 배열 두 개를 합칠 때 큰 배열에 작은 배열을 추가하는 식으로 해야 시간복잡도가 줄어든다고 하네요. 지금 생각해보면 당연한건데도 이런 생각을 못했다니 참 씁슬합니다. 공부가 부족한 것 같습니다.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


vector<vector<int>> graph;
vector<int> degree;
vector<bool> visited;
int n, m;

vector<pair<int, int>> to_add;


void dfs(int current, vector<int>& order) {
	visited[current] = true;

	for (auto& next : graph[current])
		if (!visited[next])
			dfs(next, order);

	order.push_back(current);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;

	degree.resize(n);
	graph.resize(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;

		graph[a].push_back(b);
		graph[b].push_back(a);

		++degree[a];
		++degree[b];
	}

	
	visited.resize(n);

	typedef pair<vector<int>, vector<int>> component;	// 해당 component에 있는 <홀수점, 짝수점>
	vector<component> components;
	priority_queue< pair<int, int> > pq;	// <홀수점 개수, 컴포넌트 번호>

	for (int i = 0; i < n; ++i) {
		if (!visited[i]) {
			vector<int> order;
			dfs(i, order);

			vector<int> odd_idxs, even_idxs;
			for (auto& idx : order) {
				if (degree[idx] % 2 == 1)
					odd_idxs.push_back(idx);
				else
					even_idxs.push_back(idx);
			}

			pq.emplace(odd_idxs.size(), components.size());
			components.emplace_back(move(odd_idxs), move(even_idxs));
		}
	}


	while (!pq.empty()) {
		if (pq.size() == 1) {
			break;
		}


		auto [c1_odd_cnt, c1_idx] = pq.top();	pq.pop();
		auto [c2_odd_cnt, c2_idx] = pq.top();	pq.pop();

		auto& c1 = components[c1_idx], &c2 = components[c2_idx];

		auto& c1_odds = c1.first, &c2_odds = c2.first;
		auto& c1_evens = c1.second, &c2_evens = c2.second;


		// merge two components
		//
		//      a        b
		//1 - 홀수점 - 홀수점
		//2 - 홀수점 - 짝수점
		//3 - 짝수점 - 짝수점
		int a, b;
		if (c1_odd_cnt && c2_odd_cnt) {
			a = c1_odds.back();
			b = c2_odds.back();
			c1_odds.pop_back();
			c2_odds.pop_back();
		}
		else if (c1_odd_cnt) {
			a = c1_odds.back();
			b = c2_evens.back();
			c1_odds.pop_back();
			c2_odds.push_back(b);
			c2_evens.pop_back();
		}
		else {
			a = c1_evens.back();
			b = c2_evens.back();
			c1_odds.push_back(a);
			c2_odds.push_back(b);
			c1_evens.pop_back();
			c2_evens.pop_back();
		}
		to_add.emplace_back(a, b);
		++degree[a]; ++degree[b];


		// 큰거에 작은거를 합침
		int c1_whole_cnt = c1_odds.size() + c1_evens.size();
		int c2_whole_cnt = c2_odds.size() + c2_evens.size();
		if (c1_whole_cnt > c2_whole_cnt) {
			move(c2_odds.begin(), c2_odds.end(), back_inserter(c1_odds));
			move(c2_evens.begin(), c2_evens.end(), back_inserter(c1_evens));

			pq.emplace(c1_odds.size(), c1_idx);
		}
		else {
			move(c1_odds.begin(), c1_odds.end(), back_inserter(c2_odds));
			move(c1_evens.begin(), c1_evens.end(), back_inserter(c2_evens));

			pq.emplace(c2_odds.size(), c2_idx);
		}
	}
	

	// 다 연결된 component 내부에 홀수점끼리 연결
	vector<int> odds;
	for (int i = 0; i < n; ++i) {
		if (degree[i] % 2)
			odds.push_back(i);
	}

	for (int i=0; i<odds.size(); i+=2)
		to_add.emplace_back(odds[i], odds[i+1]);


	if (to_add.empty())
		cout << "0\n" << '\n';
	else {
		cout << to_add.size() << '\n';
		for (auto& [from, to] : to_add)
			cout << from+1 << ' ' << to+1 << '\n';
	}

	return 0;
}

 

맞은 사람 소스 보니까 Union Find로 푼 사람이 많던데 아직 그 알고리즘 공부를 안해서 동일한 풀이인지 아닌지는 모르겠네요. 유니온 파인드 공부하면 한번 더 풀어봐야겠습니다.