练66.1  黑马篮球队

解题思路

先去重无向边并统计度数。按(度数,编号)从小到大把边定向，枚举有向楔u→v→w，若还存在u→w就得到三角形，计算三人的原始度数和。

正确性说明

全序定向使每个三角形有唯一最小顶点u及中间顶点v，必被u→v→w并结合u→w枚举到且仅一次。检查所有三角形取度数和最小值即最优。

易错点

重复认识只算一个朋友；求总度数不减6。题面第二行边数与样例冲突，本题按主要任务与样例输出一行最小值。

复杂度

去重后E条边，时间O(E log E+E√E)，空间O(n+E)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    set<pair<int, int>> edges;
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (x > y)
            swap(x, y);
        if (x != y)
            edges.insert({x, y});
    }
    vector<int> deg(n + 1);
    for (auto e : edges) {
        deg[e.first]++;
        deg[e.second]++;
    }
    vector<vector<int>> out(n + 1);
    for (auto e : edges) {
        int x = e.first, y = e.second;
        if (make_pair(deg[x], x) > make_pair(deg[y], y))
            swap(x, y);
        out[x].push_back(y);
    }
    vector<int> mark(n + 1);
    int ans = INT_MAX;
    for (int u = 1; u <= n; u++) {
        for (int w : out[u])
            mark[w] = u;
        for (int v : out[u])
            for (int w : out[v])
                if (mark[w] == u)
                    ans = min(ans, deg[u] + deg[v] + deg[w]);
    }
    cout << (ans == INT_MAX ? -1 : ans) << "\n";
    return 0;
}