996. 正方形数组的数目

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。

示例 1：

输入：[1,17,8]
输出：2
解释：
[1,8,17] 和 [17,8,1] 都是有效的排列。
示例 2：

输入：[2,2,2]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-squareful-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 class Solution {
 2 public:
 3 //count记录每种元素剩余的数量
 4 //Map 使用邻接表法记录图 
 5 //第i个结点与第j个结点中间有边的条件就是两个结点的值相加后是完全平方数
 6 //然后从每个结点开始都深度优先搜索 图中每个结点都只出现一次的路径（这里若一个数在A中出现两次 则图中可以访问两次这个结点）
 7     int dfs(int cur,int LeftSize,map<int,int>& count,map<int,vector<int>>& Map)
 8     {
 9         if(!LeftSize)return 1;
10         int res=0;
11         for(auto next:Map[cur])
12         {
13             if(count[next])
14             {
15                 count[next]--;
16                 res+=dfs(next,LeftSize-1,count,Map);
17                 count[next]++;
18             }
19         }
20         return res;
21     }
22     int numSquarefulPerms(vector<int>& A) {
23         int N=A.size();
24         map<int,int> count;
25         map<int,vector<int>> Map;
26         for(auto i:A)count[i]++;
27         for(auto p:count)
28             for(auto q:count)
29             {
30                 int sum=p.first+q.first;
31                 int sqrt_val=sqrt(sum);
32                 if(sqrt_val*sqrt_val==sum)
33                     Map[p.first].push_back(q.first);
34             }
35         int res=0;
36         for(auto p:count)
37         {
38             count[p.first]--;
39             res+=dfs(p.first,N-1,count,Map);
40             count[p.first]++;
41         }
42         return res;
43 
44     }
45 };