Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2014
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include<stdio.h>
  2.  
  3. #define NMAX 252
  4.  
  5. int n;
  6. int v[NMAX][NMAX];
  7.  
  8. inline void swap(int a, int b)
  9. {
  10.     int aux;
  11.     for(int j=1; j<=n; ++j)
  12.     {
  13.         aux=v[a][j];
  14.         v[a][j]=v[b][j];
  15.         v[b][j]=aux;
  16.     }
  17.     aux=v[a][n+1];
  18.     v[a][n+1]=v[b][n+1];
  19.     v[b][n+1]=aux;
  20. }
  21.  
  22. inline void elim(int a, int b)
  23. {
  24.     for(int j=1; j<=n; ++j)
  25.         v[a][j]^=v[b][j];
  26.     v[a][n+1]^=v[b][n+1];
  27. }
  28.  
  29. bool Gauss()
  30. {
  31.     int x;
  32.     for(int i=1, j=1; i<=n; ++i, ++j)
  33.     {
  34.         x=i;
  35.         while(!v[i][x])++x;
  36.  
  37.         if(x>n)
  38.             return false;
  39.  
  40.         if(x!=i)
  41.             swap(i, x);
  42.  
  43.         for(x=1; x<=n; ++x)
  44.             if(v[x][j] && x!=i)
  45.                 elim(x, i);
  46.     }
  47.  
  48.     return true;
  49. }
  50.  
  51. int main()
  52. {
  53.     freopen("date.in", "r", stdin);
  54.     freopen("date.out", "w", stdout);
  55.  
  56.     int x;
  57.  
  58.     scanf("%d", &n);
  59.  
  60.     for(int i=1; i<=n; ++i)
  61.     {
  62.         while(true)
  63.         {
  64.             scanf("%d", &x);
  65.  
  66.             if(x==-1)
  67.                 break;
  68.  
  69.             v[i][x]=1;
  70.         }
  71.         v[i][n+1]=1;
  72.     }
  73.  
  74.     if(Gauss())
  75.     {
  76.         for(int i=1; i<=n; ++i)
  77.             if(v[i][n+1])
  78.                 printf("%d ", i);
  79.         printf("\n");
  80.     }
  81.     else
  82.         printf("No solution\n");
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement