HNU13377:Book Club(DFS)
Problem description |
Porto’s book club is buzzing with excitement for the annual book exchange event! Every year, members bring their favorite book and try to find another book they like that is owned by someone willing to trade with them. Be careful, because members will not give their book without receiving one they like in return. |
Input |
The first line has two integers: N, the number of people, and M, the total number of “declarations of interest”. Each of the following M lines has two integers, A and B, indicating that member A likes the book that member B brought (0<=A,B < N). Numbers |
Output |
You should output YES if we can find a new book for every club member and NO if that is not possible. |
Sample Input |
9 9 |
Sample Output |
YES |
Problem Source |
HNU Contest |
题意:
有n个人,m种需求,给出m行,每行a,b代表a想要的书在b那里,问能不能通过交换的方法来满足每一个人的需求
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std; #define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 20005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 1000000007; int n,m,vis[N],tem[N];
vector<int> a[N]; int dfs(int u)
{
for(int i=0; i<a[u].size(); i++)
{
int v = a[u][i];
if(!vis[v])
{
vis[v]=1;
if(tem[v]==-1||dfs(tem[v]))
{
tem[v] = u;
return 1;
}
}
}
return 0;
} int main()
{
int i,j,k,x,y;
while(~scanf("%d%d",&n,&m))
{
for(i = 0; i<=n; i++)
a[i].clear();
for(i = 0; i<m; i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
}
MEM(tem,-1);
for(i = 0; i<n; i++)
{
MEM(vis,0);
dfs(i);
}
for(i = 0; i<n; i++)
{
if(tem[i]==-1)
break;
}
if(i==n)
printf("YES\n");
else
printf("NO\n");
} return 0;
}
最新文章
- [原创]cocos2d-x研习录-第二阶 概念类之场景类(CCScene)
- [Error Code: 1290. The MySQL server is running with the --secure-file-priv option so it cannot execute this statement]错误解决
- Struts2的类型转换
- 【转】PHP 之 CURL 模拟登陆并获取数据
- Hive 创建和生成Rcfile 和SequenceFile格式的表
- 揭开redis神秘面纱
- Linux基础系统优化及常用命令
- MySql 游标定义时使用临时表
- matlab练习程序(点集配准的SVD法)
- day 变量的赋值原理 变量的命名规则
- html页面跳转传递参数
- Azure IoT 预配置解决方案
- js监听浏览器tab窗口切换
- Summary: 书架问题
- ActiveMQ学习--001--ActiveMQ和消息中间件
- 一些程序OEP入口特征
- Django-模板语言和过滤器
- PHP XML Parser函数
- 转 neighbour table overflow 问题解决
- 633. Sum of Square Numbers 是否由两个完全平方数构成