【算法系列学习】巧妙建图，暴搜去重 Counting Cliques

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 
  9 using namespace std;
 10 const int maxn=105;
 11 const int maxm=1e3+5;
 12 int n,m,s;
 13 int deg[maxn];
 14 int mp[maxn][maxn];
 15 int Stack[maxn];
 16 int ans;
 17 struct Edge
 18 {
 19     int to;
 20     int next;
 21 }edge[maxm];
 22 int tot,head[maxn];
 23 void add(int u,int v)
 24 {
 25     edge[tot].to=v;
 26     edge[tot].next=head[u];
 27     head[u]=tot++;
 28  } 
 29 void Init()
 30 {
 31     ans=0;
 32     tot=0;
 33     memset(head,-1,sizeof(head));
 34     memset(deg,0,sizeof(deg));
 35     memset(mp,0,sizeof(mp));
 36     memset(Stack,0,sizeof(Stack));
 37 }
 38 bool judge(int a[],int v)
 39 {
 40     for(int i=1;i<=a[0];i++)
 41     {
 42         if(!mp[v][a[i]])    
 43         {
 44             return false;
 45         }
 46     }
 47     return true;
 48 }
 49 void DFS(int a[],int u)
 50 {
 51     if(a[0]==s)
 52     {
 53         ans++;
 54         return;    
 55     }
 56     for(int i=head[u];i!=-1;i=edge[i].next)
 57     {
 58         int v=edge[i].to;
 59         //判断这个点是不是和每个已有团结点都有边 
 60         if(judge(a,v))
 61         {
 62             //入栈 
 63             a[++a[0]]=v;
 64             DFS(a,v);
 65             a[0]--;
 66         }
 67     }
 68 }
 69 int main()
 70 {
 71     int T;
 72     scanf("%d",&T);
 73     while(T--)
 74     {
 75         Init();
 76         scanf("%d%d%d",&n,&m,&s);
 77         int u,v;
 78         for(int i=0;i<m;i++)
 79         {
 80             scanf("%d%d",&u,&v);
 81             //这是去重的关键 
 82             /*用一个数组记录已经存在的团的大小，数组是一个由小到大
 83 的数组，即前点要进入团时，判断该节点是否比团内所有点大，这样就避免了重复，判断大小时只需要判断进最后一个点是否比当前点小就行了
 84 所以建图是可以按照 小的点指向大的点得方式建图，这样会少很多不必要的搜索操作 */
 85             /*之所以可以从小的节点指向大的节点是因为，最后要找的是一个无向完全图，在无向完全图中肯定可以找到一条从小节点依次走到到大节点的有向路：比如1->2->3这样的路，边的双向信息用另一个数组存一下就行了
 86 
 87 这样就减少了大量不必要的计算，而且不会重复，因为你在一个无向完全图里只可能找到一个，v1 < v2 < v3 ... < vx
 88 这样的偏序关系的路，不可能再出现例如v2 < v1 < v3 < ... < vx这种路，因为这么多点大小的偏序关系是唯一的，确定了一次，以后都不会重复了，连标记去重都不用，真巧妙！*/
 89             if(u>v)
 90             {
 91                 swap(u,v);
 92             }
 93             add(u,v);
 94             mp[u][v]=mp[v][u]=1;
 95             //为了剪枝 
 96             deg[u]++;
 97             deg[v]++;
 98         }    
 99         for(int i=1;i<=n;i++)
100         {
101             //剪枝，度小于s-1的一定不在团内 
102             if(deg[i]<s-1)
103             {
104                 continue;
105             }
106             //模拟栈，Stack[0]保存已经确定的团结点的大小 
107             Stack[0]=1;
108             Stack[1]=i;
109             DFS(Stack,i);    
110         }
111         printf("%d
",ans);
112     }
113     return 0;    
114 }
View Code