fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. bool dfs(vector<vector<int>>& graph, vector<bool>& visited, vector<int>& d, int x){
  9. for(int i = 0; i < graph[x].size(); i++){
  10. int p = graph[x][i];
  11. if(visited[p]){
  12. continue;
  13. }
  14. visited[p] = true;
  15. if(d[p] == -1 or dfs(graph, visited, d, d[p])){
  16. d[p] = x;
  17. return true;
  18. }
  19. }
  20. return false;
  21. }
  22.  
  23. int main() {
  24.  
  25. ios_base::sync_with_stdio(0);
  26. cin.tie(0);
  27.  
  28. int n, m;
  29. cin >> n >> m;
  30.  
  31. map<string, int> member;
  32. for(int i = 1; i <= m; i++){
  33. string str;
  34. cin >> str;
  35. member[str] = i;
  36. }
  37.  
  38. vector<vector<int>> graph(n + 1);
  39. for(int i = 1; i <= n; i++){
  40. int x;
  41. cin >> x;
  42. for(int j = 0; j < x; j++){
  43. string str;
  44. cin >> str;
  45. graph[i].push_back(member[str]);
  46. }
  47. }
  48.  
  49. vector<int> d(m + 1, -1);
  50.  
  51. int answer = 0;
  52. for(int i = 1; i <= n; i++){
  53. vector<bool> visited(m + 1, false);
  54. if(dfs(graph, visited, d, i)){
  55. answer++;
  56. }
  57. }
  58.  
  59. if(answer == n){
  60. cout << "YES";
  61. }else{
  62. cout << "NO\n" << answer;
  63. }
  64.  
  65. return 0;
  66. }
Success #stdin #stdout 0s 5532KB
stdin
6 6
MIYEON
MINNIE
SOOJIN
SOYEON
YUQI
SHUHUA
2 YUQI SOOJIN
1 SOYEON
1 YUQI
2 YUQI SHUHUA
3 MIYEON SOYEON YUQI
3 MIYEON SHUHUA SOYEON
stdout
NO
5