2472.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 125 行

/* This Code is Submitted by wywcgs for Problem 2472 on 2007-04-16 at 11:08:04 */
#include <cstdio>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int N = 128;

const int INF = 1 << 28;



class Graph {

private:

	bool map[N][N], check[N];

	int n, match[N];

	bool dfs(int);

public:

	int maxMatch();

	bool solve();

};

bool Graph::dfs(int p) {

	for(int i = 0; i < n; i++) {

		if(!check[i] && map[p][i]) {

			check[i] = true;

			int t = match[i];

			match[i] = p;

			if(t == -1 || dfs(t))  return true;

			match[i] = t;

		}

	}

	return false;

}

int Graph::maxMatch() {

	memset(match, -1, sizeof(match));

	int mth = 0;

	for(int i = 0; i < n; i++) {

		memset(check, false, sizeof(check));

		if(dfs(i)) mth++;

	}

	return mth;

}

bool Graph::solve() {

	int a, b; scanf("%d %d", &a, &b);

	if(a == 0) exit(0);

	n = max(a, b);

	memset(map, false, sizeof(map));

	for(int i = 0; i < b; i++) {

		int m; scanf("%d", &m);

		for(int j = 0; j < m; j++) {

			int c; scanf("%d", &c);

			map[i][c] = true;

		}

	}

	return maxMatch() == a;

}



Graph g;



int main()

{


	while(true) printf("%s\n", g.solve() ? "yes" : "no");

	return 0;

}