sdut离散题目13

柔光的暖阳◎ 2022-06-18 08:54 167阅读 0赞

think:  
1自反：在关系矩阵中主对角线元素键值为1  
2反自反：在关系矩阵中主对角线元素键值为0  
3对称：在关系矩阵中关于主对角线对称的元素的键值相等  
4反对称：在关系矩阵中关于主对角线对称的元素的键值不同时为1

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

Problem Description  
DaYu平时只顾着看电影，没有学习离散，学期末快考试的时候才慌了神，因为时间不够，因此他决定只复习一个知识点，但是他发现他一个知识点都不会，因此他跑过来请你帮他解决一个问题。求一个集合是否是自反的。

Input  
第一行输入组数T(T<10)，每组的第一行输入集合元素个数m(m < 100)和对应关系个数n(n < 100)，集合中元素为1,2,…,m，接下来n行每行输入两个数x，y(0 < x, y < 100)

Output  
如果满足自反关系，则输出true，否则输出false。

Example Input  
2  
5 9  
1 1  
1 2  
2 2  
3 3  
2 3  
4 4  
4 5  
5 5  
5 1  
5 8  
1 1  
1 2  
2 2  
3 3  
2 3  
4 4  
4 5  
5 1

Example Output  
true  
false

Hint

Author

以下为Accepted代码——建议参考

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int T, m, n, i, x, y, flag;
        int ans[104][104];
        scanf("%d", &T);
        while(T--)
        {
            flag = 1;
            memset(ans, 0, sizeof(ans));
            set<int> s;
            set<int>::iterator it;
            scanf("%d %d", &m, &n);
            for(i = 0; i < n; i++)
            {
                scanf("%d %d", &x, &y);
                ans[x][y] = 1;
                s.insert(x);
            }
            for(it = s.begin(); it != s.end(); it++)
            {
                if(ans[*it][*it] != 1)
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
                printf("true\n");
            else
                printf("false\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 192KB
    Submit time: 2017-04-02 18:32:08
    ****************************************************/

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int T, m, n, i, x, y, flag;
        int ans[104][104];
        scanf("%d", &T);
        while(T--)
        {
            flag = 1;
            memset(ans, 0, sizeof(ans));
            scanf("%d %d", &m, &n);
            for(i = 0; i < n; i++)
            {
                scanf("%d %d", &x, &y);
                ans[x][y] = 1;
            }
            for(i = 1; i <= m; i++)
            {
                if(ans[i][i] != 1)
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
                printf("true\n");
            else
                printf("false\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-04-02 18:27:15
    ****************************************************/