Advertisement
atulshgl

Maximum Clique

Mar 25th, 2014
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<stdlib.h>
  6. #include<algorithm>
  7. #include<limits.h>
  8. #include<list>
  9. using namespace std;
  10. int adj[21][21],m,s[21];
  11. int clique(int s[],int l)
  12. {
  13.     int i,j,deg[l],mini;
  14.     while(1)
  15.     {
  16.         int minn=l+5,maxx=0;
  17.         memset(deg,0,sizeof(deg));
  18.         for(i=0;i<l;i++)
  19.         {
  20.             for(j=0;j<l;j++)
  21.             {
  22.                 if(adj[s[i]][s[j]] && i!=j)
  23.                 {
  24.                     deg[i]++;
  25.        //             cout<<"i="<<s[i]<<" j="<<s[j]<<endl;
  26.                 }
  27.             }
  28.        
  29.         }
  30.     /*    cout<<"deg==>"<<endl;
  31.         for(i=0;i<l;i++)
  32.             cout<<deg[i]<<" ";
  33.         cout<<endl;
  34.     */    for(i=0;i<l;i++)
  35.         {
  36.             if(deg[i]<minn)
  37.                 minn=deg[i],mini=i;
  38.             if(deg[i]>maxx)
  39.                 maxx=deg[i];
  40.         }
  41.     //    cout<<"min="<<minn<<" max="<<maxx<<endl;
  42.      //   system("pause");
  43.         if(minn==maxx)
  44.             return l;
  45.         else
  46.         {
  47.             l--;
  48.             for(i=1;i<mini;i++)
  49.                 s[i]=s[i];
  50.             for(;i<=l;i++)
  51.                 s[i]=s[i+1];
  52.         }
  53.     }
  54. }
  55. int main()
  56. {
  57.     int m,i,j,maxx=0;
  58.     cin>>m;
  59.    for(i=0;i<m;i++)
  60.    {
  61.      for(j=0;j<m;j++)
  62.        cin>>adj[i][j];
  63.     }
  64.   /*  for(i=0;i<m;i++)
  65.     {
  66.         for(j=0;j<m;j++)
  67.             cout<<adj[i][j]<<" ";
  68.         cout<<endl;
  69.     }
  70.   */  for(i=0;i<m;i++)
  71.     {
  72.         int s[21]={i},len=1;
  73.     //    cout<<"i===>"<<i+1<<endl;
  74.         for(j=0;j<m;j++)
  75.             if(adj[i][j])
  76.                 s[len++]=j;//,cout<<j+1<<" ";
  77.       //  cout<<"len="<<len<<endl;
  78.         maxx=max(maxx,clique(s,len));
  79.     }
  80.     cout<<maxx;
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement