ulvis.paste.net

Paste Search Dynamic
Recent pastes
matrix
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. // matrix is 1 based.
  8.  
  9. bool matrix[50][50]={false};
  10.  
  11. void addfriend(int a, int b) {
  12.     matrix[a][b] = true;
  13.     matrix[b][a] = true;  
  14. }
  15.  
  16. void unfriend(int a, int b) {
  17.     matrix[a][b] = false;
  18.     matrix[b][a] = false;  
  19. }
  20.  
  21. void n(int x) {
  22.     int count=0;
  23.     for(int i=1; i<50; i++) {
  24.         if(matrix[x][i]) {
  25.             count++;
  26.         }
  27.     }
  28.     cout << count << "\n";
  29. }
  30.  
  31. void f(int x) {
  32.     set<int> friends;
  33.     set<int> foff;
  34.    
  35.     friends.insert(x);
  36.  
  37.     //add to set friends
  38.     for(int i=1; i<50; i++) {
  39.         if(matrix[x][i]) {
  40.             if(friends.count(i) == 0) {
  41.                 friends.insert(i);
  42.             }
  43.         }
  44.     }
  45.    
  46.     //loop through friends of friends
  47.     for(int i=1; i<50; i++) {
  48.         if(matrix[x][i]) {
  49.             for(int j=1; j<50; j++) {
  50.                 if(matrix[i][j]) {
  51.                     if(friends.count(j) == 0) {
  52.                         if(foff.count(j) == 0) {
  53.                             foff.insert(j);
  54.                         }
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.     }
  60.     cout << foff.size() << "\n";
  61. }
  62.  
  63.  
  64. //washall
  65. void s(int x, int y) {
  66.     int dist[50][50];
  67.     for(int i=1; i<50; i++) {
  68.         for(int j=1; j<50; j++) {
  69.             if(i==j) {
  70.                 dist[i][j] = 0;
  71.             } else if(matrix[i][j]) {
  72.                 dist[i][j] = 1;
  73.             } else {
  74.                 dist[i][j] = 1000; //infinity
  75.             }
  76.         }
  77.     }
  78.     for(int k=1; k<50; k++) {
  79.         for(int i=1; i<50; i++) {
  80.             for(int j=1; j<50; j++) {
  81.                 if(dist[i][j] > dist[i][k] + dist[k][j]) {
  82.                     dist[i][j] = dist[i][k] + dist[k][j];
  83.                 }
  84.             }
  85.         }
  86.     }
  87.    
  88.     if(dist[x][y]==1000) {
  89.         cout << "Not connected\n";
  90.     } else {
  91.         cout << dist[x][y] << "\n";
  92.     }
  93. }
  94.  
  95. int main() {
  96.     cin.sync_with_stdio(0);
  97.     cin.tie(0);
  98.    
  99.     addfriend(1, 6);
  100.     addfriend(2, 6);
  101.     addfriend(3, 6);
  102.     addfriend(3, 4);
  103.     addfriend(3, 5);
  104.     addfriend(3, 15);
  105.     addfriend(4, 6);
  106.     addfriend(5, 6);
  107.     addfriend(6, 7);
  108.     addfriend(7, 8);
  109.     addfriend(8, 9);
  110.     addfriend(9, 10);
  111.     addfriend(9, 12);
  112.     addfriend(10, 11);
  113.     addfriend(11, 12);
  114.     addfriend(12, 13);
  115.     addfriend(13, 15);
  116.     addfriend(13, 14);
  117.     addfriend(16, 17);
  118.     addfriend(17, 18);
  119.     addfriend(16, 18);
  120.    
  121.     char command;
  122.     cin >> command;
  123.     while(command != 'q') {
  124.         int x, y;
  125.        
  126.         switch(command) {
  127.             case 'i':
  128.                 cin >> x >> y;
  129.                 addfriend(x, y);
  130.                 break;
  131.             case 'd':
  132.                 cin >> x >> y;
  133.                 unfriend(x, y);
  134.                 break;
  135.             case 'n':
  136.                 cin >> x;
  137.                 n(x);
  138.                 break;
  139.             case 'f':
  140.                 cin >> x;
  141.                 f(x);
  142.                 break;
  143.             case 's':
  144.                 cin >> x >> y;
  145.                 s(x, y);
  146.         }
  147.        
  148.         cin >> command;
  149.     }
  150.  
  151.     return 0;
  152. }
Parsed in 0.025 seconds