D. Exploration

정점의 개수가 $N$개고 간선의 개수가 $M$개인 그래프가 주어진다. 각 정점의 차수가 $K$ 이상인 부분그래프 중 가장 큰 부분그래프의 크기를 구하는 문제다.

입력으로 주어진 그래프에서 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없으므로 제거한다. 그런 정점들을 제거하면 새로운 그래프가 나오는데, 마찬가지로 새로운 그래프에서도 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없다.

위와 같은 방법으로 더 이상 제거할 정점이 없을 때까지 정점들을 제거한다. 그 후 남은 그래프가 문제에서 요구하는 최대 크기의 부분그래프가 된다. 총 시간복잡도는 $O(M)$이 된다.

#include <stdio.h> #include <vector> using namespace std; #define MAXN 2001 int T, N, M, K; int deg[MAXN]; bool V[MAXN]; vector <int> con[MAXN]; void del(int n) { if (V[n]) return; V[n] = 1; for (int t: con[n]){ if (!V[t] && --deg[t] < K) del(t); } } int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &N, &K, &M); for (i=1;i<=N;i++) deg[i] = V[i] = 0; for (i=1;i<=M;i++){ scanf("%d%d", &j, &k); deg[j]++; deg[k]++; con[j].push_back(k); con[k].push_back(j); } for (i=1;i<=N;i++) if (deg[i] < K) del(i); int ans = 0; for (i=1;i<=N;i++) if (!V[i]) ans++; printf("%d\n", ans); } }