解题思路

• 将每个数看作一个点，若 ai & aj != 0 则两点间连一条无向边，求图的最短环长度（环的最小长度为 3）。

• 关键剪枝：若某一位的置位数量 ≥ 3，则这三个点两两都有该位相连，答案必为 3。又因为最高只需考虑 0~60 位（ai ≤ 1e18），若非零数的个数 m > 120，按抽屉原理必有某位出现 ≥3 次，直接输出 3。

• 否则每一位最多出现 2 次，非零点数 m ≤ 120。此时可以把这些点显式建图：

  • 对所有两两点判断一次按位与是否为正，若是则加边。
  • 用 BFS 从每个起点求最短环：BFS 过程中若遇到已访问且不是父亲的点 v，就发现了一个环，长度更新为 dist[u] + dist[v] + 1。

• 若最终没有发现环，输出 -1。

相关算法：位运算+抽屉原理剪枝，BFS 求无向图最短环。

复杂度分析

• 统计每一位出现次数：O(n * 60)。
• 若 m ≤ 120，建图 O(m^2)，从每个点 BFS：O(m * (m + E))，最坏 m ≤ 120 时约为 O(m^3)，上界也就百万级操作，完全可行。
• 额外空间：图与 BFS 队列 O(m^2)（最坏完全图）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
from collections import deque

# 外部函数：返回最短环长度
def shortest_cycle(nums):
    # 过滤零（与任何数都不连边）
    b = [x for x in nums if x != 0]
    m = len(b)
    if m == 0:
        return -1

    # 统计每一位出现次数，若有 >=3 直接返回 3
    cnt = [0] * 61
    for x in b:
        for k in range(61):
            if (x >> k) & 1:
                cnt[k] += 1
    if any(c >= 3 for c in cnt):
        return 3

    # 若非零数超过120，必有答案为3（抽屉原理）
    if m > 120:
        return 3

    # 显式建无向图
    g = [[] for _ in range(m)]
    for i in range(m):
        for j in range(i + 1, m):
            if (b[i] & b[j]) != 0:
                g[i].append(j)
                g[j].append(i)

    INF = 10 ** 9
    ans = INF

    # 从每个点 BFS，寻找最短环
    for s in range(m):
        dist = [INF] * m
        fa = [-1] * m
        q = deque([s])
        dist[s] = 0
        while q:
            u = q.popleft()
            for v in g[u]:
                if dist[v] == INF:
                    dist[v] = dist[u] + 1
                    fa[v] = u
                    q.append(v)
                elif fa[u] != v:  # 遇到非父边，形成环
                    ans = min(ans, dist[u] + dist[v] + 1)
        if ans == 3:  # 已经是最优
            break

    return -1 if ans == INF else ans


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    nums = data[1:1 + n]
    print(shortest_cycle(nums))

if __name__ == "__main__":
    main()

Java

// 注意：ACM 风格，类名为 Main
import java.io.*;
import java.util.*;

// 自定义快读以应对 n 可到 1e6
public class Main {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is){ in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c; do { c = read(); } while (c <= ' '); // 跳过空白
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    // 外部函数：返回最短环长度
    static int shortestCycle(long[] nums) {
        ArrayList<Long> b = new ArrayList<>();
        for (long x : nums) if (x != 0) b.add(x);
        int m = b.size();
        if (m == 0) return -1;

        // 统计每一位出现次数
        int[] cnt = new int[61];
        for (long x : b) {
            for (int k = 0; k <= 60; k++) {
                if (((x >> k) & 1L) == 1L) cnt[k]++;
            }
        }
        for (int c : cnt) if (c >= 3) return 3;
        if (m > 120) return 3;

        // 建图
        ArrayList<Integer>[] g = new ArrayList[m];
        for (int i = 0; i < m; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                if ( (b.get(i) & b.get(j)) != 0 ) {
                    g[i].add(j);
                    g[j].add(i);
                }
            }
        }

        final int INF = 1 << 29;
        int ans = INF;

        // 多源 BFS（逐点作为起点）
        for (int s = 0; s < m; s++) {
            int[] dist = new int[m];
            int[] fa = new int[m];
            Arrays.fill(dist, INF);
            Arrays.fill(fa, -1);
            ArrayDeque<Integer> q = new ArrayDeque<>();
            dist[s] = 0; q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : g[u]) {
                    if (dist[v] == INF) {
                        dist[v] = dist[u] + 1;
                        fa[v] = u;
                        q.add(v);
                    } else if (fa[u] != v) {
                        ans = Math.min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
            if (ans == 3) break;
        }
        return ans == INF ? -1 : ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = (int) fs.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextLong();
        System.out.println(shortestCycle(a));
    }
}

C++

// ACM 风格：读入、输出在主函数，核心逻辑在外部函数
#include <bits/stdc++.h>
using namespace std;

// 外部函数：返回最短环长度
int shortest_cycle(const vector<long long>& nums) {
    vector<long long> b;
    for (auto x : nums) if (x != 0) b.push_back(x);
    int m = (int)b.size();
    if (m == 0) return -1;

    // 统计每一位出现次数，出现 >=3 直接为 3
    int cnt[61] = {0};
    for (auto x : b) {
        for (int k = 0; k <= 60; ++k)
            if ((x >> k) & 1LL) cnt[k]++;
    }
    for (int k = 0; k <= 60; ++k) if (cnt[k] >= 3) return 3;
    if (m > 120) return 3; // 抽屉原理

    // 建图（m ≤ 120）
    vector<vector<int>> g(m);
    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
            if ( (b[i] & b[j]) != 0 ) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    const int INF = 1e9;
    int ans = INF;

    // 从每个点 BFS，寻找最短环
    for (int s = 0; s < m; ++s) {
        vector<int> dist(m, INF), fa(m, -1);
        queue<int> q;
        dist[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (dist[v] == INF) {
                    dist[v] = dist[u] + 1;
                    fa[v] = u;
                    q.push(v);
                } else if (fa[u] != v) {
                    ans = min(ans, dist[u] + dist[v] + 1);
                }
            }
        }
        if (ans == 3) break;
    }
    return ans == INF ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << shortest_cycle(a) << "\n";
    return 0;
}

题目内容

考虑一个有 $n$ 个节点的图，每个节点对应一个整数，其有 $n$ 个整数

$a_1,a_2,a_3,…,a_n$ ，当且仅当 $a_i$ & $a_j≠0$ 时表示节点 $i$ 和节点 $j(i≠j)$ 之间有一条边，其中 & 表示按位与操作。

例如:

$3$ & $6:3$ 的二进制表示是 $0 1 1$ ，$6$ 的二进制表示是 $110$，$3$ ＆ $6=2$ (二进制 $010$ )不为 $0$ ，表示 $3$ 和 $6$ 之间有一条边。

$3$ & $28:3$ 的二进制表示是 $00011$，$28$ 的二进制表示是 $11100$ ，$3$ ＆ $28=0$ ，表示 $3$ 和 $28$ 之间没有边。

请找出该图中最短的环的长度(环的最小长度是 $3$ )，如果图中没有环输出 $-1$ 。

输入描述

第一行输入一个整数 $n(1≤n≤10^6)$ ，表示数字的个数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(0≤a_i≤10^{18})$，表示数字序列。(输入的数字有可能重复)

输出描述

如果图中没有环，输出 $-1$ 。

否则输出最短环的长度。

样例1

输入

10
448 0 112 0 0 0 28 260 3 0

输出

4

说明

$448$ $112$ $28$ $260$ $3$ 的二进制表示为:

$448:111000000$

$112:001110000$

$28:000011100$

$260:100000100$

$3:000000011$

$448$ $-112$ $-28$ $-260$ 构成环，长度为 $4$ 。

样例2

输入

1
1000000000000000000

输出

-1

说明

一个节点无法构成环

样例3

输入

4
1 2 4 8

输出

-1

说明

$1$ $2$ $4$ $8$ 的二进制表示为:

$1:0001$

$2:0010$

$4:0100$

$8:1000$

节点之间两两没有连接，无法构成环。

样例4

输入

4
3 6 28 5

输出

3

说明

$3$ $6$ $28$ $5$ 的二进制表示为:

$3:00011$

$6:00110$

$28:11100$

$5:00101$

$3$ 和 $6$ 相连，$6$ 和 $28$ 相连，$5$ 和 $3$ 相连，$3-6-5$ 构成了一个环，长度为 $3$

样例5

输入

4
3 6 28 9

输出

4

说明

$3$ $6$ $28$ $9$ 的二进制表示为:

$3:00011$

$6:00110$

$28:11100$

$9:01001$

$3$ 和 $6$ 相连，$6$ 和 $28$ 相连，$28$ 和 $9$ 相连，$9$ 和 $3$ 相连，$3-6-28-9$ 构成了一个环，长度为 $4$