离散题目16——自反闭包

分手后的思念是犯贱 2022-06-18 10:19 229阅读 0赞

think:  
1二维矩阵+自反闭包定义  
[什么是自反闭包 —— 百度百科][Link 1]

[sdut题目链接][sdut]

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

Problem Description  
给出集合A,以及集合A上的关系R,求关系R的自反闭包。

Input  
首先输入t,表示有t组数据.  
每组数据第一行输入n,表示A中有n个数据,接下来一行输入n个数,(4 <= n < 100, 0 < Ai < 100)  
第二行输入m,代表R中有m对关系(0 < m < 100)  
接下来m行每行输入x,y代表< x,y >这对关系.(从小到大给出关系,如果x相同,按y排列)

Output  
输出题目要求的关系集合,每行输出一对关系,输出顺序按照中的x大小非递减排列,假如x相等按照y大小非递减排列.  
每组数据末尾额外输出一行空行。

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

Example Output  
1 1  
1 2  
2 2  
2 3  
3 3  
4 4  
4 5  
5 1  
5 5

Hint

Author  
Johsnows

以下为Presentation Error代码——每组数据输出后应再输出一行空行

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int T, n, m, t, x, y, ans[104][104];
        scanf("%d", &T);
        while(T--)
        {
            set<int> s;
            memset(ans, 0, sizeof(ans));
            scanf("%d", &n);
            while(n--)
            {
                scanf("%d", &t);
                s.insert(t);
            }
            scanf("%d", &m);
            while(m--)
            {
                scanf("%d %d", &x, &y);
                if(s.count(x) && s.count(y))
                {
                    ans[x][y] = 1;
                    ans[x][x] = 1;
                    ans[y][y] = 1;
                }
            }
            for(int i = 1; i <= 100; i++)
            {
                for(int j = 1; j <= 100; j++)
                {
                    if(ans[i][j] == 1)
                        printf("%d %d\n", i, j);
                }
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Presentation Error
    Take time: 12ms
    Take Memory: 196KB
    Submit time: 2017-04-04 20:38:25
    ****************************************************/

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int T, n, m, t, x, y, ans[104][104];
        scanf("%d", &T);
        while(T--)
        {
            set<int> s;
            memset(ans, 0, sizeof(ans));
            scanf("%d", &n);
            while(n--)
            {
                scanf("%d", &t);
                s.insert(t);
            }
            scanf("%d", &m);
            while(m--)
            {
                scanf("%d %d", &x, &y);
                if(s.count(x) && s.count(y))
                {
                    ans[x][y] = 1;
                    ans[x][x] = 1;
                    ans[y][y] = 1;
                }
            }
            for(int i = 1; i <= 100; i++)
            {
                for(int j = 1; j <= 100; j++)
                {
                    if(ans[i][j] == 1)
                        printf("%d %d\n", i, j);
                }
            }
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 12ms
    Take Memory: 196KB
    Submit time: 2017-04-04 20:39:33
    ****************************************************/

[Link 1]: https://zhidao.baidu.com/question/122321671.html
[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2083/pid/3810