50025. Independent People

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
 
int n, m;
int graph[105][105];
bool can_choose[105];
bool choosen[105];
 
inline static void choose_person(int p, int temp_arr[]){
    choosen[p] = true;
    for(int i = 0; i < n; i++)temp_arr[i] = can_choose[i];
    for(int i = 0; i < n; i++) if(graph[p][i] == 1) can_choose[i] = false;
}
inline static void revert_person(int p, int temp_arr[]){
    choosen[p] = false;
    for(int i = 0; i < n; i++) can_choose[i] = temp_arr[i];
}
inline static void print_choosen(){
    bool flag = true;
    for(int i = 0; i < n; i++){
        if(choosen[i] == true){
            if(flag) printf("%d", i);
            else printf(" %d", i);
            flag = false;
        }
    }
    printf("\n");
}
 
bool solve(int level, int start){
    if(level == m) return true;
 
    int can_choose_num = 0;
    for(int i = start; i < n; i++) if(can_choose[i] == true) can_choose_num += 1;
    if(can_choose_num + level < m) return false;
 
    for(int i = start; i < n; i++){
        if(can_choose[i] == false || choosen[i] == true) continue;
 
        int temp_arr[105];
        choose_person(i, temp_arr);
        if(solve(level + 1, start + 1) == true) return true;
        revert_person(i, temp_arr);
    }
    return false;
}
 
int main(){
    while(scanf("%d %d", &n, &m) != EOF){
        for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &graph[i][j]);
 
        for(int i = 0; i < n; i++){
            choosen[i] = false;
            can_choose[i] = true;
        }
 
        if(solve(0, 0) == true) print_choosen();
        else printf("no solution\n");
    }
}

#include <stdio.h>
#include <stdlib.h>
 
int n, k;
int g[105][105];
 
void print_arr(int arr[], int n){
    if(n == 0) return;
    printf("%d", arr[0]);
    for(int i = 1; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}
 
int solve(int cdt[], int cdt_size, int ans[], int ans_size){
    if(ans_size == k){
        print_arr(ans, ans_size);
        return 1;
    }
 
    if(cdt_size == 0) return 0;
    if(cdt_size + ans_size < k) return 0;
 
    int cdt_choose[105], cdt_choose_size = 0;
    for(int i = 1; i < cdt_size; i++){
        if(g[cdt[0]][cdt[i]] == 0){
            cdt_choose[cdt_choose_size] = cdt[i];
            cdt_choose_size++;
        }
    }
 
    int ans_choose[105], ans_choose_size = ans_size  + 1;
    for(int i = 0; i < ans_size; i++){
        ans_choose[i] = ans[i];
    }
    ans_choose[ans_size] = cdt[0];
 
 
    return solve(cdt + 1, cdt_size - 1, ans, ans_size) || solve(cdt_choose, cdt_choose_size, ans_choose, ans_choose_size);
 
}
 
int main(){
    while(scanf("%d %d", &n, &k) == 2){
        for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &g[i][j]);
 
        int cdt[105], cdt_size = n;
        for(int i = 0; i < n; i++) cdt[i] = i;
 
        int ans[105], ans_size = 0;
        if(!solve(cdt, cdt_size, ans, ans_size)) printf("no solution\n");
    }
}