Posted on 2008-04-22 10:02
superman 閱讀(330)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1140 C++ 00:07.18 928K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, match[301];
7 bool map[301][301], visited[301];
8
9 bool dfs(int p)
10 {
11 for(int i = 1; i <= m; i++)
12 if(map[p][i] && visited[i] == false)
13 {
14 visited[i] = true;
15 if(match[i] == 0 || dfs(match[i]))
16 {
17 match[i] = p;
18 return true;
19 }
20 }
21 return false;
22 }
23
24 int main()
25 {
26 int cases; cin >> cases;
27 while(cases--)
28 {
29 memset(map, false, sizeof(map));
30 memset(visited, false, sizeof(visited));
31 memset(match, 0, sizeof(match));
32
33 cin >> n >> m;
34
35 int cnt, t;
36 for(int s = 1; s <= n; s++)
37 {
38 cin >> cnt;
39 while(cnt--)
40 {
41 cin >> t;
42 map[s][t] = true;
43 }
44 }
45
46 cnt = 0;
47 for(int i = 1; i <= n; i++)
48 {
49 memset(visited, false, sizeof(visited));
50 cnt += dfs(i);
51 }
52 cout << (cnt == n ? "YES" : "NO") << endl;
53 }
54
55 return 0;
56 }
57