离散题目12

ゞ浴缸里的玫瑰 2022-06-18 09:41 161阅读 0赞

think:  
1getline()+ string + stringstream  
2自己初始代码超时原因——此题目后台评测数据中可能出现输入结束后空格回车情况

[sdut题目链接][sdut]

离散题目12  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给出两个集合，以及两个集合上的关系。判断该关系能不能构成函数

Input  
多组输入。第一行数字表示集合A；第二行数字表示集合B；第三行一个数字N，表示关系的个数。以下N行，每行两个数字a b，用来描述关系a→b。0 < n < = 20000,集合A、B的大小不超过10000.

Output  
每组数据输出一行，所给关系属于函数，输出’yes’ ，否则输出‘no’。

Example Input  
1 2 3  
4 5 6  
3  
1 4  
2 5  
3 6  
1 2 3  
4 5 6  
3  
1 4  
1 5  
1 6

Example Output  
yes  
no

Hint

Author

以下为Time limit exceed代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    set<int> s1, s2;
    string aaaa;
    
    bool red();
    
    int main()
    {
        int n, x, y;
        while(red())
        {
            scanf("%d", &n);
            int flag = true;
            map<int, int> m;
            while(n--)
            {
                scanf("%d %d", &x, &y);
                if(s1.count(x) && s2.count(y))
                {
                    if(m.count(x) != 0 && m[x] != y)
                        flag = false;
                    else
                        m[x] = y;
                }
                else
                    flag = false;
            }
            if(flag)
                printf("yes\n");
            else
                printf("no\n");
            //getline(cin, aaaa);
            ///getchar();//超时
        }
        return 0;
    }
    
    bool red()
    {
        s1.clear(), s2.clear();
        string si;
        if(!getline(cin, si))
            return false;
    
        stringstream ss(si);
        int t;
        while(ss >> t)
        {
            s1.insert(t);
        }
    
        getline(cin, si);
        ss.clear();
        ss.str(si);
        while(ss >> t)
        {
            s2.insert(t);
        }
        return true;
    }
    
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 1010ms
    Take Memory: 0KB
    Submit time: 2017-04-03 21:29:05
    ****************************************************/

以下为Time limit exceed代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    set<int> s1, s2;
    string aaaa;
    
    bool red();
    
    int main()
    {
        int n, x, y;
        while(red())
        {
            scanf("%d", &n);
            int flag = true;
            map<int, int> m;
            while(n--)
            {
                scanf("%d %d", &x, &y);
                if(s1.count(x) && s2.count(y))
                {
                    if(m.count(x) != 0 && m[x] != y)
                        flag = false;
                    else
                        m[x] = y;
                }
                else
                    flag = false;
            }
            if(flag)
                printf("yes\n");
            else
                printf("no\n");
            //getline(cin, aaaa);
            getchar();
        }
        return 0;
    }
    
    bool red()
    {
        s1.clear(), s2.clear();
        string si;
        if(!getline(cin, si))
            return false;
    
        stringstream ss(si);
        int t;
        while(ss >> t)
        {
            s1.insert(t);
        }
    
        getline(cin, si);
        ss.clear();
        ss.str(si);
        while(ss >> t)
        {
            s2.insert(t);
        }
        return true;
    }
    
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 1010ms
    Take Memory: 0KB
    Submit time: 2017-04-03 21:27:33
    ****************************************************/

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    set<int> s1, s2;
    string aaaa;
    
    bool red();
    
    int main()
    {
        int n, x, y;
        while(red())
        {
            scanf("%d", &n);
            int flag = true;
            map<int, int> m;
            while(n--)
            {
                scanf("%d %d", &x, &y);
                if(s1.count(x) && s2.count(y))
                {
                    if(m.count(x) != 0 && m[x] != y)
                        flag = false;
                    else
                        m[x] = y;
                }
                else
                    flag = false;
            }
            if(flag)
                printf("yes\n");
            else
                printf("no\n");
            getline(cin, aaaa);
            ///getchar();//超时
        }
        return 0;
    }
    
    bool red()
    {
        s1.clear(), s2.clear();
        string si;
        if(!getline(cin, si))
            return false;
    
        stringstream ss(si);
        int t;
        while(ss >> t)
        {
            s1.insert(t);
        }
    
        getline(cin, si);
        ss.clear();
        ss.str(si);
        while(ss >> t)
        {
            s2.insert(t);
        }
        return true;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 52ms
    Take Memory: 1336KB
    Submit time: 2017-04-03 21:29:24
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2083/pid/3806