离散题目10

离散题目10
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic
Problem Description

给定一个数学函数F和两个集合A,B,写一个程序来确定函数是满射。 如果每个可能的像至少有一个变量映射其上(即像集合B中的每个元素在A中都有一个或一个以上的原像)，或者说值域任何元素都有至少有一个变量与之对应，那这个映射就叫做满射。

Input

多组输入直到文件结束，对于每组输入，第一行先输入一个n（A集合里的元素个数），m（B集合里的元素个数），k（F数学函数关系的条数）。
0 < n,m < 10000, 0 < k < n;
第二行输入有n个元素，分别为a1到an；
第三行输入有m个元素，分别为b1到bn；
接下来输入有k行，分别为集合A到B的关系
Output

（一组答案占一行）
当满足满射关系时输出Yes。
不满足关系时输出No。
Example Input

5 3 5
1 3 5 7 8
2 5 6
1 2
3 6
5 5
7 2
8 6
Example Output

Yes
Hint

#include<bits/stdc++.h>

using namespace std;

int a[10010],b[10010];
int search(int a[],int low,int high,int key)
{
    int mid = (low+high)/2;
    if(low<=high)
    {
        if(a[mid]==key)
            return mid;
        else if(a[mid]<key)
            return search(a,mid+1,high,key);
        else
            return search(a,low,mid-1,key);
    }
    else
        return -1;
}
set<int> s;
int main()
{
    int n,m,q;
    while(cin>>n>>m>>q)
    {
        s.clear();
        int ok = 1;
        int x,y;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i = 0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i = 0;i<m;i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i = 0;i<q;i++)
        {
            scanf("%d %d",&x,&y);
            if(search(a,0,n-1,x)==-1)
            {
                ok = 0;
            }
            if(search(b,0,m-1,y)==-1)
            {
                ok = 0;
            }
            else
            {
                s.insert(y);
            }
        }
        if(ok&&s.size()==m)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
}