codeforces #580 div2 D - Shortest Cycle (무방향그래프 사이클, 비둘기집)

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

 

undirected graph이고, 최대 1e5개의 정점에 대해 만들어지는 사이클 크기의 최소값을 구하는 문제이다.

 

오픈카톡에 따르면 무방향그래프에서 사이클을 모두 구하는 것에 대한 알고리즘은 매우 어렵다. ( 불가능하지 않냐고 물어보는 사람도 있었다. ) 하지만 지금 문제에선 사이클 크기의 최소값을 구하는 것이므로 알고리즘을 짤 수 있다.

 

1) 사이클 크기의 최소값 구하기

서로 연결돼 있는 i,j에 대해, 그 간선을 끊었을 때 i~j의 경로 길이 + 1(자기자신)이 사이클 크기이다. 이를 모든 간선에 대해 적용하며 mn값을 갱신해 나가면 된다. 즉, adj[i][j]=adj[j][i]=0 -> mn = min( dist[i][j], mn ) -> adj[i][j] = adj[j][i]=1 순의 로직을 모든 i,j에 대해 적용하면 된다.

 

하지만 위와 같은 방법의 시간복잡도는 O(m * (mlogN)이다. 최대 정점의 개수가 1e5이므로 한참 시간 초과가 난다. 

 

2) pigeon hole principle

입력값들을 모두 이진수로 본다면, xth 비트가 3번 이상 나온 상황이라면 항상 크기 3이하의 사이클이 생긴다. 

 

입력 값이 1e18까지 들어오는데, 이는 60비트로 나타낼 수 있다. 비둘기집 법칙에 따라서, 0이 아닌 값 60개 이상이 들어온다면, xth 비트가 2번 이상 나오는 경우가 반드시 존재하고, 0이 아닌 값 120개 이상이 들어온다면 xth비트가 3번 이상 나오는 경우가 반드시 존재한다.

 

따라서 0이 아닌 입력이 120개 이상이라면 무조건 최소크기(3)의 사이클이 생길 수 밖에 없다. (0도 입력으로 들어오므로 잘 처리 해줘야 함)

 

 

#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAX = 122;
const int INF = 1e9;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n = 0, num;  cin >> num; //num : 입력정점수, n:0이아닌 입력값 개수

	bool adj[MAX][MAX] = { 0 };
	ll arr[MAX];
	for (int i = 0; i < num; i++) {
		ll input; cin >> input;
		if (input == 0) continue;	 //입력값 0은 무시해도 좋다. 그어떤 요소와도 연결x
		if (n > 120) break;
		arr[++n] = input;
	}

	if (n > 120) {
		cout << 3 << '\n';
		return 0;
	}
    //정점수 120이하에 대해서만 생각해 주면 된다.

	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			if ((arr[i] & arr[j]) != 0) 			
				adj[i][j] = adj[j][i] = true;

	int mn = 1e9;
	for (int i = 1; i < n; i++) {
		for (int j = i+1; j <= n; j++) {
			if (!adj[i][j]) continue;
			adj[i][j] = adj[j][i] = 0; //연결을 끊어줬을 때 최소 거리를 구함.

			int dist[MAX];
			fill(dist, dist + MAX, INF);
			dist[i] = 0;
			bool visited[MAX] = { 0 };

			priority_queue<P, vector<P>, greater<P>> pq;
			pq.push({ dist[i] , i });
			while (!pq.empty()) {
				int curr;
				do {
					curr = pq.top().second;
					pq.pop();
				} while (!pq.empty() && visited[curr]);
				if (visited[curr]) break;

				visited[curr] = true;

				for (int next = 1; next <= n; next++) {
					if (!adj[curr][next] || curr==next) continue;
					int d = 1;
					if (dist[next] > dist[curr] + d) {
						dist[next] = dist[curr] + d;
						pq.push({ dist[next],next });
					}
				}
			}
            
			adj[i][j] = adj[j][i] = true; //다시 연결해주기
			mn = min(mn, dist[j]);
		}
	}
	cout << (mn>=INF ? -1 : mn+1) << '\n';
}

 

 

 

무방향그래프사이클, php, 다익스트라, bit 등 여러 개념 포함된 좋은 문제인 것 같다.

 

간선을 지웠다 붙였다 해야하므로 인접행렬을 사용해서 구현했는데, 인접리스트를 잘만 쓰면 조금 더 시간복잡도를 줄일 수 있을 것 같다.

 

시점과 종점이 정해져 있고 가중치가 모두 양수(1)인 상황이므로 최단거리를 구하는 알고리즘으로 다익스트라를 사용했는데, n값이 충분히 작으니까 그냥 bfs돌려도 될것 같다.

 

위 방법대로 한다면 사이클 크기의 최대값도 찾을 수 있을 것이다. 

 

<참고>

directed graph에서 사이클 찾기.

https://blog.naver.com/kks227/220785731077