将每个数看作一个点,若 ai & aj != 0 则两点间连一条无向边,求图的最短环长度(环的最小长度为 3)。
关键剪枝:若某一位的置位数量 ≥ 3,则这三个点两两都有该位相连,答案必为 3。又因为最高只需考虑 0~60 位(ai ≤ 1e18),若非零数的个数 m > 120,按抽屉原理必有某位出现 ≥3 次,直接输出 3。
否则每一位最多出现 2 次,非零点数 m ≤ 120。此时可以把这些点显式建图:
v,就发现了一个环,长度更新为 dist[u] + dist[v] + 1。若最终没有发现环,输出 -1。
考虑一个有 n 个节点的图,每个节点对应一个整数,其有 n 个整数
a1,a2,a3,…,an ,当且仅当 ai & aj=0 时表示节点 i 和节点 j(i=j) 之间有一条边,其中 & 表示按位与操作。
例如:
3 & 6:3 的二进制表示是 011 ,6 的二进制表示是 110,3 & 6=2 (二进制 010 )不为 0 ,表示 3 和 6 之间有一条边。