Математические свойства множеств

Question

Пусть ? — множество целых чисел от 1 до ?. Задано отношение ? на множестве ? × ?. Отношение задаётся списком принадлежащих ему элементов: множеством пар (?, ?) ∈ ? ×?. Для заданного отношения ? требуется определить:

Является ли ? функцией: ∀? ∈ ?: (?, ?) ∈ ? и (?, ?) ∈ ? ⇒ ? = ? — отсутствует многозначность.
Является ли ? всюду определённой функцией: ? является функцией и ∀? ∈ ? ∃ ? | (?, ?) ∈ ? — значение определно на всём множестве ?.
Является ли ? инъекцией: (?, ?) ∈ ? и (?, ?) ∈ ? ⇒ ? = ?.
Является ли ? сюръекцией: ∀? ∈ ? ∃ ? | (?, ?) ∈ ?.
Является ли ? биекцией: отношение ? и инъективно, и сюръективно.

Первая строка входного файла содержит два целых числа ? и ?, записанных через пробел — размер множества (1 <= ? <= 300) и количество пар (1 <= ? <= ?^2). В следующих ? строках записано по два целых числа ? и ? (1 <= ?, ? <= ?) — элементы отношения ?. Гарантируется, что все пары различны. Если отношение ? не удовлетворяет ни одному из описанных свойств, то выведите число 0. В противном случае выведите через пробел в порядке увеличения номера свойств, которыми обладает отношение ?.

P.S.Я думала над этой задачей до 4 утра, но ничего толкового в голову не пришло. Единственное, что я поняла - нужно сделать двумерный массив и там смотреть пары по парам. Помогите пожалуйста, умоляю, что тут вообще можно сделать???

Answer 1

Ну, тогда примерно так...

Проверьте, если нет - давайте пароль, там зарегистрироваться мало :) - буду разбираться... все ж таки написан этот код со скоростью набора на клавиатуре, и не тестирован - запросто мог ошибиться.

#include <stdio.h>

int debug_log = 0;

int R[301][301];
int N, M;

void is_1234(int * n1, int * n2, int * n3, int * n4)
{
    *n1 = *n2 = *n3 = *n4 = 1;
    for(int x = 1; x <= N; ++x)
    {
        int s = 0, q = 0;
        for(int y = 1; y <= N; ++y)
        {
            s+= R[x][y];
            q+= R[y][x];
        }

        if (debug_log) printf("Row %d, sum = %d\n",x,s);

        if (*n1 && s >  1) *n1 = 0;   // Не должно быть двух 1 в одной строке - для 1
        if (*n2 && s == 0) *n2 = 0;   // Не должно быть пустых строк для 2
        if (*n3 && q >  1) *n3 = 0;   // Не должно быть двух 1 в одном столбце
        if (*n4 && q == 0) *n4 = 0;   // Не должно быть пустых столбцов для 4

        if (*n1 == 0) *n2 = 0;
        if (*n1 == 0) *n4 = 0;

        if (*n1 == 0 &&
            *n2 == 0 &&
            *n3 == 0 &&
            *n4 == 0) break;
    }
    if (debug_log) printf("_1 = %d\n",*n1);
}

int main()
{
    scanf("%d %d",&N,&M);
    for(int i = 0; i < M; ++i)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        R[x][y] = 1;
    }

    if (debug_log)
        for(int x = 0; x <= N; ++x)
        {
            for(int y = 0; y <= N; ++y)
            {
                printf("%d  ",R[x][y]);
            }
            puts("\n");
        }

    int n1, n2, n3, n4, n5;
    is_1234(&n1,&n2,&n3,&n4);
    if (debug_log) printf("n1 = %d\n", n1);

    n5 = n3 && n4;

    if (n1+n2+n3+n4+n5==0) puts("0");
    else
    {
        if (n1) printf("%d ",1);
        if (n2) printf("%d ",2);
        if (n3) printf("%d ",3);
        if (n4) printf("%d ",4);
        if (n5) printf("%d ",5);
    }
}

Update

Немного я ошибся (не дочитал условие), немного - вы (например, выводить надо не 6, а 0, если ничего не работает), немного - они (например, в решении сюръекция должна быть функцией, но они это не написали).

Все, новый код принималкой :) принят.

БЛОГ НА HUSL

Математические свойства множеств

Ответы (1 шт):