对于数组中每一对数(u, v),如果它们是squareful的,则在节点u和节点v之间连一条边。节点0是超级源点,与每个节点都相连。
建图后,枚举起点,计算可以一次性不重复走完整个图的次数。
class Solution {
public:
vector<vector<int>> adj;
vector<bool> visited;
int n, ans = 0;
bool check(int x, int y){
int a = (int) sqrt(x+y);
return a*a == x+y;
}
void dfs(vector<int>& A, int u, int len){
if (len == n){
ans++;
return;
}
for (int i = 0; i<adj[u].size(); i++){
int &v = adj[u][i];
if (visited[v]) continue;
if (i > 0 && A[v-1] == A[adj[u][i-1]-1] && !visited[adj[u][i-1]]) continue;
visited[v] = true;
dfs(A, v, len + 1);
visited[v] = false;
}
}
int numSquarefulPerms(vector<int>& A) {
n = A.size();
sort(A.begin(), A.end());
adj.resize(n+1);
visited.resize(n+1, false);
for (int i = 1; i<=n; i++) adj[0].push_back(i);
for (int i = 1; i<=n; i++)
for (int j = i+1; j<=n; j++)
if (check(A[i-1], A[j-1])){
adj[i].push_back(j);
adj[j].push_back(i);
}
dfs(A, 0, 0);
return ans;
}
};