Bipartite_Graph

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18214 번역 문제 번역 # Susan은 식탁 정리는 잘하지만, 사무실 책상 정리는 잘 못합니다. Susan은 방금 일련의 문서들에 대한 서류 작업을 마쳤고, 문서들은 여전히 책상에 쌓여 있습니다. 문서들은 일련번호가 있으며, 상사가 가져왔을 때는 순서대로 쌓여 있었습니다. 그러나 지금은 순서가 완벽하지 않은데, Susan이 너무 게을러서 더미에서 빠져나온 문서들을 제자리에 다시 넣지 않았기 때문입니다. 작업이 끝났다는 소식을 듣고, 상사는 그녀에게 보내고 있는 문서 상자에 문서들을 즉시 반납하기를 원합니다. 물론 문서들은 일련번호 순서대로 상자에 보관되어야 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23569 번역 문제 번역 # 문제 설명 # 사람들 간의 상호작용이 주어질 때, 정점이 사람들이고 두 사람이 서로 친구인 경우에만 그들 사이에 간선이 있는 그래프를 정의할 수 있습니다. 이러한 그래프를 소셜 네트워크라고 하며, 예를 들어 대학의 학생들이나 작은 마을의 주민들과 같은 모든 사람들의 집합에 대해 잘 정의됩니다. 최근 몇 년간 소셜 네트워크를 분석하는 완전한 과학 분야가 생겨났는데, 이는 사람들과 그들의 행동에 대한 많은 흥미로운 측면들이 이 친구 관계 그래프의 속성으로 가장 잘 이해되기 때문입니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1154 🧐 관찰 및 접근 # A / B팀으로 나누는걸 보면 당연히 이분그래프를 떠올릴 수 있겠는데.. 같은 그룹의 학생들끼리는 모두 서로 아는 사이여야 한다? 우리가 아는 이분그래프의 정의랑 뭔가 느낌이 다르다! 저 말을 다시한번 생각해보자 같은 그룹의 학생이다 -> 서로 아는사이이다 이 문장의 대우명제는? 서로 모르는 사이이다 -> 다른 그룹의 학생이다 그렇다면, 그래프의 간선을 뒤집어버리자! $N$은 최대 1000이므로, 간선 $M = N^2$개는 충분히 계산할 수 있다. 이렇게 간선을 뒤집은 그래프를 여 그래프, 혹은 complement graph라고 한다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N; while(1){ int u, v; cin >> u >> v; if(u == -1 && v == -1) break; know[u][v] = know[v][u] = true; } bool isBipartite = true; vector<int> color(N+1, 0); rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); rep(nxt, 1, N+1){ if(cur == nxt) continue; if(know[cur][nxt]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ isBipartite = false; break; } } } } if(!isBipartite){ cout << -1; return; } vector<int> team1, team2; rep(i, 1, N+1){ if(color[i] == 1) team1.push_back(i); else team2.push_back(i); } cout << 1 << "\n"; for(auto x: team1) cout << x << " "; cout << -1 << "\n"; for(auto x: team2) cout << x << " "; cout << -1 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23086 🧐 관찰 및 접근 # 그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다. 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다. 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다. 이때 시간 복잡도는 $O(K(N+M))$이다. 이는 너무 느리다! 문제 상황을 조금 더 관찰해보자. $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다. $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다! **매개변수 탐색(파라메트릭 서치)**가 가능하다. 💻 풀이 # 코드 (C++): int N, M, K; vector<pair<int, int>> links[100010]; // (nxt, idx) vector<int> prohibit_list; int color[100010]; // 0: unvisited, 1: group A, 2: group B bool prohibited[200010]; bool isBipartite(int cnt){ rep(i, 1, M+1) prohibited[i] = false; rep(i, 0, cnt) prohibited[prohibit_list[i]] = true; rep(i, 1, N+1) color[i] = 0; rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto [nxt, idx]: links[cur]){ if(prohibited[idx]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ return false; } } } } return true; } void solve(){ cin >> N >> M >> K; rep(i, 1, M+1){ int u, v; cin >> u >> v; links[u].push_back({v, i}); links[v].push_back({u, i}); } rep(i, 0, K){ int p; cin >> p; prohibit_list.push_back(p); } // 모두 금지했을때 이분 그래프인가? if(!isBipartite(K)){ cout << -1; return; } // 파라메트릭 서치 int ok = K, ng = -1; while(ok - ng > 1){ int mid = (ok + ng) >> 1; if(isBipartite(mid)) ok = mid; else ng = mid; } cout << ok << "\n"; int groupA_sz = 0, groupB_sz = 0; isBipartite(ok); rep(i, 1, N+1) color[i] == 1 ? groupA_sz++ : groupB_sz++; cout << min(groupA_sz, groupB_sz) << ' ' << max(groupA_sz, groupB_sz) << "\n"; } 🔒 구현 코드 잠금