题目
题意：给出n个点，对n个点连n-1条边要求构成一棵树，其中对于树中属于同一帮派的点不能相互连边。则我们只需对所有的点进行连边尝试，直到连了n-1条边即可。遇到同一个帮派的点或已经连接的点直接跳过即可。(题目数据不大直接暴力就过了)
AC code
#include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #define pii pair<int,int> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const int Max = 1e6 + 5; int lst[Max]; int ls[Max][2]; int main() { FAST; int t;cin >>t; while (t--) { map<int, int> ma;//ma用来标记哪些点已经连接 int n;cin >> n; for (int i = 1;i <= n;i++)cin >> lst[i]; int g = 0; for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { if (g == n - 1)break;//已连n-1条边 if (ma[i]&&ma[j])//两点已在 { continue; } else { if (lst[i] == lst[j])continue;//相同帮派跳过 else { ma[i]++,ma[j]++; ls[++g][0] = i, ls[g][1] = j; } } } } if (g != n - 1) cout << "NO" << endl; else { cout << "YES" << endl; for (int i = 1;i <= g;i++)cout << ls[i][0] << " " << ls[i][1] << endl; } } }