Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 30th, 2012  |  syntax: C  |  size: 1.44 KB  |  hits: 19  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #define LIM 99
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5.  
  6. int max, nv, ne[LIM];
  7. char edges[LIM][LIM];
  8.  
  9. void BronKerbosch(char r[], char p[], char x[]) {
  10.         int i, j, pivot, deg=0;
  11.         char nr[LIM], np[LIM], nx[LIM];
  12.        
  13.         if(p[0] == 0 && x[0] == 0) {
  14.                 if(r[0] > max) max = r[0];
  15.                 return;
  16.         }
  17.        
  18.         for(i = 1; i <= nv; i++) {
  19.                 if(p[i] && ne[i] >= deg) {
  20.                         pivot = i;
  21.                         deg = ne[i];
  22.                 }
  23.         }
  24.        
  25.         for(i = 1; i <= nv; i++) {
  26.                 if(p[i] && !edges[pivot][i]) {
  27.                         p[i] = 0;
  28.                         p[0]--;
  29.                         if(ne[i] >= r[0]) {
  30.                                 np[0] = 0;
  31.                                 nx[0] = 0;
  32.                                 for(j = 1; j <= nv; j++) {
  33.                                         np[j] = p[j] & edges[i][j];
  34.                                         np[0] += np[j];
  35.                                         nx[j] = x[j] & edges[i][j];
  36.                                         nx[0] += nx[j];
  37.                                 }
  38.                                 memcpy(nr, r, nv+1);
  39.                                 nr[i] = 1;
  40.                                 nr[0]++;
  41.                                 BronKerbosch(nr, np, nx);
  42.                         }
  43.                         x[i] = 1;
  44.                         x[0]++;
  45.                 }
  46.         }
  47. }
  48.  
  49. int main() {
  50.         int i, j, t = 0;
  51.         char r[LIM], p[LIM], x[LIM];
  52.         while(1) {
  53.                 scanf("%d", &nv);
  54.                 if(!nv) break;
  55.                 for(i = 1; i <= nv; i++) {
  56.                         ne[i] = nv-1;
  57.                         for(j = 1; j <= nv; j++)
  58.                                 edges[i][j] = 1;
  59.                 }              
  60.                 r[0] = 0;
  61.                 p[0] = nv;
  62.                 x[0] = 0;
  63.                 for(i = 1; i <= nv; i++) {
  64.                         r[i] = 0;
  65.                         p[i] = 1;
  66.                         x[i] = 0;
  67.                         edges[i][i] = 0;
  68.                         while(1) {
  69.                                 scanf("%d", &j);
  70.                                 if(!j) break;
  71.                                 if(edges[i][j]) ne[i]--;
  72.                                 edges[i][j] = 0;
  73.                                 if(edges[j][i]) ne[j]--;
  74.                                 edges[j][i] = 0;
  75.                         }
  76.                 }
  77.                 max = 0;
  78.                 BronKerbosch(r, p, x);
  79.                 printf("Teste %d\n%d\n\n", ++t, max);
  80.         }
  81.         return 0;
  82. }
create a new version of this paste RAW Paste Data