scpc2016_pre1_3.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>

using namespace std;

#define MAXN 110

int K, L, N, M;
int graph[MAXN][MAXN], degree[MAXN];

//정점 v를 그래프에서 제거한다.
void remove(int v){
    for(int i = 1 ; i <= N ; i++){
        degree[i] -= graph[i][v];
        graph[i][v] = graph[v][i] = 0;
    }
    degree[v] = -100;
}

//차수가 K미만인 정점을 지운다.
bool removeUnder(){
    for(int i =1 ; i<= N ; i++){
        if(degree[i] >= 0 && degree[i] < K){
            remove(i);
            return true;
        }
    }
    return false;
}

//차수가 |V|-L이상인 정점을 찾는다.
int findUpper(){
    int nowVertexNum = 0;
    for(int i =1 ; i<= N; i++)
        nowVertexNum += ( degree[i] >= 0);
    
    if(nowVertexNum == 0)
        return -1;
    
    for(int i =1; i<= N; i++){
        if(degree[i] >= nowVertexNum - L ){
            return i;
        }
    }
    return -1;
}

int main(){
    setbuf(stdout, NULL);
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t++){
        memset(graph, 0 , sizeof(graph));
        memset(degree, 0, sizeof(degree));
        
        scanf("%d%d%d%d", &K, &L, &N, &M);
        for(int i =1 ;i<= M; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            graph[a][b] = graph[b][a] = 1;
            degree[a]++, degree[b]++;
        }
        
        while(1){
            //현재 그래프에서 차수가 K미만인 정점을 모두 지움
            while(removeUnder());
            
            //현재 그래프에서 차수가 |V|-L 이상인 정점을 찾음
            int upperVertex = findUpper();
            
            //없으면 종료, 있으면 지우고 반복
            if(upperVertex == -1)
                break;
            else
                remove(upperVertex);
        }
        
        int ans = 0;
        for(int i = 1; i<= N ; i++)
            if(degree[i] < 0)
                ans += i;
        
        printf("Case #%d\n%d\n", t, ans);
    }
    return 0;
}