Submission #1983952

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int check(vector<int> group, int p);
int check_relation(int x, int y);

vector<vector<int>> relation;

int main() {
    int N, M;
    cin >> N >> M;


    int x, y;
    for (int i=0; i<M; i++) {
        cin >> x >> y;
        relation.emplace_back(vector<int> {x, y});
    }

    queue<vector<int>> Q;

    for (int n=1; n<N; n++)         // n=N は入れない
        Q.push(vector<int> {n});
    
    vector<int> group;
    int last_person;
    int result = 1;

    while (!Q.empty()) {
        group = Q.front();
        last_person = group.back();     // last_person=Nのものはキューにpushしない前提
        for (int p = last_person + 1; p<=N; p++) {
            if (check(group, p)) {
                group.push_back(p);
                Q.push(group);
                result = (group.size() > result) ? group.size() : result;
                //cout << group.size() << endl;         
            }
        }
        Q.pop();
    }

    cout << result << endl;

}

int check(vector<int> group, int p) {
    int result = 1;
    
    int p_num = group.size();
    for (int i=0; i<p_num; i++) {
        if(!check_relation(group[i], p)){
            result = 0;
            break;
        }
    }

    return result;
}

int check_relation(int x, int y) {
    int result = 0;

    for (int i=0; i<relation.size(); i++) {
        if (relation[i][0] == x && relation[i][1] == y) result = 1;
    }

    return result;
}

Submission Info

Judge Result