Submission #4034302

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<queue>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll,ll> LLP;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define INF 1000000000007
#define MOD 1000000007
#define ARRAY_MAX 3005


int main(){

    int n,m;
    cin >> n >> m;
    vector<int> x(m),y(m);
    set<pii> st;

    for(int i = 0;i < m;i++){
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
        st.insert(pii(x[i],y[i]));
        st.insert(pii(y[i],x[i]));
        st.insert(pii(x[i],x[i]));
        st.insert(pii(y[i],y[i]));
    }

    int maxi = 1;
    for(int i = 0;i < (1 << n);i++){
        vector<int> vec;
        bool exist = true;

        for(int j = 0;j < n;j++){
            if((i>>j) & 1){
                vec.push_back(j);
            }
        }

        for(int k = 0;k < vec.size();k++){
            for(int l = k+1;l < vec.size();l++){
                if(st.find(pii(vec[k],vec[l])) == st.end()){
                    //知り合いではない
                    exist = false;
                }else if(st.find(pii(vec[l],vec[k])) == st.end()){
                    //知り合いではない
                    exist = false;
                }
            }
        }

        if(exist){
            //派閥が存在
            maxi = max(maxi,(int)vec.size());
        }
        vec.shrink_to_fit();
    }

    cout << maxi << endl;






    return 0;
}

Submission Info

Judge Result