Educational codeforces #78 D - Segment Tree (라인스위핑)

https://codeforces.com/contest/1278/problem/D

풀이가 너무 생소해서 정리해둠

 

<문제설명>

최대 5e5개의 정점이 입력된다. 정점은 [l,r]의 정보를 담고 있다. 서로 교차되는(intersect) 정점들이 서로 이어져있다고 할 때, 그 그래프가 트리인지 아닌지를 출력하는 문제.

ex) 정점[1,3]과 [2,4]는 이어져있다. 하지만 [1,2],[3,4]는 이어져 있지 않다.

+모든 끝점은 유일하다. 예를들어 [1,2][2,3]이 동시에 주어지는 경우는 없다

 

 

 

<풀이>

1. 각 정점의 정보를 P a[MAX]에 담아둔다.

 

2. vector<P> evs에 (a[i].first, i) 와 (a[i].second, i)를 모두 담아서 오름차순 정렬한다.

 

3. set<P> cand를 마련한다. (아직 교차할 정점을 찾을 여지가 남은 정점의 (끝점, 정점번호)를 기억해 두기 위함.)

 

4. 정렬해둔 evs를 차례로 순차하면서 ( for(P p : evs) )

  4-1. cand에 p가 있는 경우 cand에서 p를 지운다.

       (이제 p가 가리키는 정점은 더이상 교차할 정점을 찾을 리 없으므로) 

 

  4-2-1. cand에 p가 없는 경우 p가 시작점이든 끝점이든 일단 p가 속한 정점(u = p.second)의 시작점 끝점을 마련해둔다.

  4-2-2. cand를 차례로 순차하면서, ( for(P q : cand) ) q가 속한 정점(v = q.second)의 끝점이 u의 끝점보다 작을 때에 대해서만 u와 v의 간선을 이어준다.

  아래와 같은 상황은 4-1에서 해결했기 때문에 일어나지 않는다!

 

5. 간선을 이어줄 때 마다 cnt++ 하여 간선 수를 cnt에 기억해 둔다.

 

6. 첫 번째 정점부터 dfs해서 모든 정점을 방문할수 있고, cnt==n-1일 때 YES 출력한다.

 

 

<코드>

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int N = 5e5 + 10;
 
int n;
P a[N];
vector<int> adj[N];
bool used[N];
 
void dfs(int curr, int prev = -1) {
	used[curr] = true;
	for (int next : adj[curr]) {
		if (next == prev || used[next]) continue;
		dfs(next, curr);
	}
}
 
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> a[i].first >> a[i].second;
 
	vector<P> evs;
	for (int i = 0; i < n; i++) {
		evs.push_back({ a[i].first,i });
		evs.push_back({ a[i].second,i });
	}
	sort(evs.begin(), evs.end());
 
	set<P> cand;
	int cnt = 0;
	for (P p : evs) {
		if (cand.count(p)) cand.erase(p);
		else {
			int u = p.second;
			int lu = a[u].first, ru = a[u].second;
			for (P q : cand) { //min-heap, 기준
				int v = q.second;
				int lv = a[v].first, rv = a[v].second;
				if (rv > ru) break;
 
				adj[u].push_back(v);
				adj[v].push_back(u);
				cnt++;
				if (cnt >= n) break;
			}
			cand.insert({ ru, u });
		}
	}
 
	dfs(0);
	if (cnt == n - 1 && count(used, used + n, 1) == n) {
		cout << "YES\n";
	}
	else {
		cout << "NO\n";
	}
}

 

<생각>

라인스위핑은 항상 어렵다.

 

위 논리도 결국 n^2이다.. 트리인지검사하는것이므로 최대 n개 간선만 이어주는것이라 시간초과가 안난다.