题意

给你一个$r*c$的矩阵，然后这个矩阵每一列有两个格子是白色的，然后你在每列上开一枪，可以打这列的任意的白色格子，问你打到的格子所在的行数是不是包括所有行了，如果包括所有行输出你在$1-c$列打抢的格子的行，当然这可以是不唯一的， 如果打不到就输出$NO$ 题目首先给出有几组数据，对于每组数据第一行代表$r$和$c$，接下来$c$行有两个数，代表这行的哪两列是白色格子

思路

和以前那个经典的二分匹配差不多，就是在一行打一枪可以消灭所有行那个题目，很容易想到二分匹配，我们将白色格子的行指向列，然后求最大匹配，用行去匹配列，看是否能够得到的匹配数是r，如果是r的话则代表所有的行都可以被打到，然后每列对应的行，如果匹配数不是$r$就输出$NO$ 当然有特例，如果$r>c$，这种情况开c抢根本不可能达到$r$行，所以直接输出$NO$

标程

#include <iostream>
#include <cstring>

using namespace std;

#define MAXV 1010

int r, c;
bool map[MAXV][MAXV], use[MAXV];
int vx[MAXV], vy[MAXV];

bool dfs(int x) {
    int i;
    for (i = 1; i <= c; i++) {
        if (map[x][i] && !use[i]) {
            use[i] = 1;
            if (vy[i] == -1 || dfs(vy[i])) {
                vy[i] = x;
                vx[x] = i;
                return true;
            }
        }
    }
    return false;
}

int hungary() {
    int i, num = 0;
    memset(vx, -1, sizeof(vx));
    memset(vy, -1, sizeof(vy));
    for (i = 1; i <= r; i++) {
        if (vx[i] == -1) {
            memset(use, 0, sizeof(use));
            if (dfs(i)) num++;
        }
    }
    return num;
}

int main() {
    int Case, i, a, b, j;
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d%d", &r, &c);
        memset(map, 0, sizeof(map));
        for (i = 1; i <= c; i++) {
            scanf("%d%d", &a, &b);
            map[a][i] = 1;
            map[b][i] = 1;
        }
        if (c < r || hungary() != r) {
            printf("NO\n");
        } else {
            for (j = 1; j <= c; j++) {
                if (vy[j] != -1) {
                    printf("%d ", vy[j]);
                } else {
                    for (i = 1; i <= r; i++) {
                        if (map[i][j]) {
                            printf("%d ", i);
                            break;
                        }
                    }
                }
            }
            printf("\n");
        }
    }
    return 0;
}