Submission #1511581

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
#ifdef _MSC_VER
#pragma push_macro("long")
#undef long
#ifdef _WIN32
inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; }
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; }
inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); }
#ifdef _WIN64
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#else
inline unsigned int hidword(unsigned long long x) { return static_cast<unsigned int>(x >> 32); }
inline unsigned int lodword(unsigned long long x) { return static_cast<unsigned int>(x & 0xFFFFFFFF); }
inline unsigned long long __builtin_ctzll(unsigned long long x) { return lodword(x) ? __builtin_ctz(lodword(x)) : __builtin_ctz(hidword(x)) + 32; }
inline unsigned long long __builtin_clzll(unsigned long long x) { return hidword(x) ? __builtin_clz(hidword(x)) : __builtin_clz(lodword(x)) + 32; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { return lodword(x) ? __builtin_ffs(lodword(x)) : hidword(x) ? __builtin_ffs(hidword(x)) + 32 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __builtin_popcount(lodword(x)) + __builtin_popcount(hidword(x)); }
#endif // _WIN64
#endif // _WIN32
#pragma pop_macro("long")
#endif // _MSC_VER
 
 
 
struct MaxClique {
	static const int MV = 210;
	int V, ans;
	int el[MV][MV / 30 + 1];
	int dp[MV];
	int s[MV][MV / 30 + 1];
	vector<int> sol;
	void init(int v) {
		V = v; ans = 0;
		memset(el, 0, sizeof(int) * MV * (MV / 30 + 1));
		memset(dp, 0, sizeof(int) * MV);
	}
	/* Zero Base */
	void addEdge(int u, int v) {
		if (u > v) swap(u, v);
		if (u == v) return;
		el[u][v / 32] |= (1 << (v % 32));
	}
	bool dfs(int v, int k) {
		int c = 0, d = 0;
		for (int i = 0; i<(V + 31) / 32; i++) {
			s[k][i] = el[v][i];
			if (k != 1) s[k][i] &= s[k - 1][i];
			c += __builtin_popcount(s[k][i]);
		}
		if (c == 0) {
			if (k > ans) {
				ans = k;
				sol.clear();
				sol.push_back(v);
				return 1;
			}
			return 0;
		}
		for (int i = 0; i<(V + 31) / 32; i++) {
			for (int a = s[k][i]; a; d++) {
				if (k + (c - d) <= ans) return 0;
				int lb = a&(-a), lg = 0;
				a ^= lb;
				while (lb != 1) {
					lb = (unsigned int)(lb) >> 1;
					lg++;
				}
				int u = i * 32 + lg;
				if (k + dp[u] <= ans) return 0;
				if (dfs(u, k + 1)) {
					sol.push_back(v);
					return 1;
				}
			}
		}
		return 0;
	}
	int solve() {
		for (int i = V - 1; i >= 0; i--) {
			dfs(i, 1);
			dp[i] = ans;
		}
		return ans;
	}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
 
 
 
MaxClique mc;
int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    
    mc.init(N);
    rep(i, 0, M) {
        int x, y; cin >> x >> y;
        x--; y--;
        mc.addEdge(x, y);
    }
    cout << mc.solve() << endl;
}

Submission Info

Judge Result