邻接表
#include<iostream>
using namespace std;
int g[333][333], vis[333], lin[333], n;
int find(int node) {
for (int i = 1; i <= g[node][0]; i++)
if (!vis[g[node][i]]) {
vis[g[node][i]] = 1;
if (!lin[g[node][i]] || find(lin[g[node][i]])) {
lin[g[node][i]] = node;
return 1;
}
}
return 0;
}
int main() {
int cas, i, j, x, p;
cin >> cas;
while (cas--) {
memset(g, 0, sizeof g);
cin >> p >> n;
for (i = 1; i <= p; i++) {
int m;
cin >> m;
for (j = 1; j <= m; j++)
cin >> g[i][++g[i][0]];
}
memset(lin, 0, sizeof lin);
for (i = 1; i <= p; i++) {
memset(vis, 0, sizeof vis);
if (!find(i))break;
}
if (i <= p)cout << "NO" << endl;
else cout << "YES" << endl;
}
}
邻接矩阵
1 #include<iostream>
2 using namespace std;
3 int g[333][333], vis[333], lin[333], n;
4
5 int find(int node){
6 for (int i = 1; i <= n; i++)
7 if (!vis[i] && g[node][i]) {
8 vis[i] = 1;
9 if (!lin[i] || find(lin[i])) {
10 lin[i] = node;
11 return 1;
12 }
13 }
14 return 0;
15 }
16
17 int main(){
18 int cas, i, j, x, p;
19 cin >> cas;
20 while (cas--) {
21 memset(g, 0, sizeof g);
22 cin >> p >> n;
23 for (i = 1; i <= p; i++) {
24 int m;
25 cin >> m;
26 for (j = 1, x; j <= m; j++)
27 cin >> x, g[i][x] = 1;
28 }
29 memset(lin, 0, sizeof lin);
30 for (i = 1; i <= p; i++) {
31 memset(vis, 0, sizeof vis);
32 if (!find(i))break;
33 }
34 if (i <= p)cout << "NO" << endl;
35 else cout << "YES" << endl;
36 }
37 }
38