SHARE
TWEET

Untitled

a guest May 19th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.    
  7. typedef struct osoba {
  8.     int number;
  9.     int stopien;
  10. } typ;
  11.  
  12. int oblicz_stopien(int macierz[], int vert, typ wierzcholek[]) {
  13.     int max = 0;
  14.     int sum = 0;
  15.  
  16.     for (int i = 0; i < vert; i++) {
  17.         for (int j = 0; j < vert; j++) {
  18.             sum += macierz[i*vert + j];
  19.         }
  20.         wierzcholek[i].number = i;
  21.         wierzcholek[i].stopien = sum;
  22.         if (sum > max)
  23.             max = sum;
  24.         sum = 0;
  25.     }
  26.     return max;
  27. }
  28.  
  29. void sort_stopien(int vert, typ wierzcholek[])
  30. {
  31.     int a, b;
  32.     for (int i = 0; i < vert; i++)
  33.     {
  34.         for (int j = 0; j < vert - 1; j++)
  35.         {
  36.             if (wierzcholek[j].stopien < wierzcholek[j + 1].stopien) {
  37.                 a = wierzcholek[j].number;
  38.                 wierzcholek[j].number = wierzcholek[j + 1].number;
  39.                 wierzcholek[j + 1].number = a;
  40.                 b = wierzcholek[j].stopien;
  41.                 wierzcholek[j].stopien = wierzcholek[j + 1].stopien;
  42.                 wierzcholek[j + 1].stopien = b;
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. int assign_colors(int arr[], int vert, typ wierzcholek[]) {
  49.     int* colors;
  50.     int end = 0;
  51.     colors = new int[vert];
  52.  
  53.     for (int i = 0; i < vert; i++)
  54.         colors[i] = 0;
  55.     colors[wierzcholek[0].number] = 1;
  56.  
  57.     for (int i = 1; i < vert; i++) {
  58.         int x = wierzcholek[i].number;
  59.         for (int j = 1; j <= vert; j++) {
  60.             for (int k = 0; k < vert; k++) {
  61.                 if (arr[x*vert + k] == 1 && colors[k] == j) break;
  62.                 else if (k == vert - 1) {
  63.                     colors[x] = j;
  64.                     end = 1;
  65.                 }
  66.             }
  67.             if (end == 1) {
  68.                 end = 0;
  69.                 break;
  70.             }
  71.         }
  72.     }
  73.     int max = 0;
  74.     for (int i = 0; i < vert; i++) {
  75.         if (colors[i] > max)
  76.             max = colors[i];
  77.     }
  78.     delete[] colors;
  79.     return max;
  80. }
  81.  
  82.  
  83. int main() {
  84.     typ* wierzcholek;
  85.  
  86.     int reps, vert;
  87.     string mat;
  88.     cin >> reps;
  89.     for (int i = 0; i < reps; i++) {
  90.         int* arr;
  91.  
  92.         cin >> vert;
  93.         cin >> mat;
  94.         arr = new int[vert*vert];
  95.         wierzcholek = new typ[vert];
  96.  
  97.         for (int j = 0; j < vert*vert; j++) {
  98.             if (mat[j] == '0')
  99.                 arr[j] = 0;
  100.             else
  101.                 arr[j] = 1;
  102.         }
  103.         int rank, chrom;
  104.         rank = oblicz_stopien(arr, vert, wierzcholek);
  105.         sort_stopien(vert, wierzcholek);
  106.         chrom = assign_colors(arr, vert, wierzcholek);
  107.         if (chrom > rank) cout << "True" << endl;
  108.         else cout << "False" << endl;
  109.         delete[] arr;
  110.     }
  111.  
  112.     return 0;
  113. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top