SHARE
TWEET

Untitled

a guest Feb 22nd, 2017 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <string>
  5.  
  6. using namespace std;
  7. bool used[100];
  8. queue<int> Q;
  9.  
  10. pair<int, int> BFS(int start, vector<int> graph[]) {
  11.     int ans = 0;
  12.     int ansV = 1;
  13.     used[start] = true;
  14.     Q.push(start);
  15.    
  16.     while (!Q.empty()) {
  17.         int u = Q.front();
  18.         Q.pop();
  19.         for (int i = 0; i < graph[u].size(); i++) {
  20.             ans++;
  21.             int v = graph[u][i];
  22.             if (!used[v]) {
  23.                 ansV++;
  24.                 used[v] = true;
  25.                 Q.push(v);
  26.             }
  27.         }
  28.     }
  29.    
  30.     return pair<int, int>(ans / 2, ansV);
  31. }
  32.  
  33. class Permatchd2 {
  34. public:
  35.     int fix(vector<string> graph) {
  36.         int n = graph.size();
  37.         vector<int> newGraph[n + 2];
  38.        
  39.         for (int i = 1; i <= n; i++)
  40.             newGraph[i].resize(0);
  41.            
  42.         for (int i = 0; i < n; i++) {
  43.             for (int j = i + 1; j < n; j++) {
  44.                 if (graph[i][j] == 'Y') {
  45.                     newGraph[i + 1].push_back(j + 1);
  46.                     newGraph[j + 1].push_back(i + 1);
  47.                 }
  48.             }
  49.         }
  50.        
  51.         int odd = 0, klika = 0, even = 0;
  52.         for (int i = 1; i <= n; i++) {
  53.             if (!used[i]) {
  54.                 pair<int, int> p = BFS(i, newGraph);
  55.                 if (p.first % 2 == 1) {
  56.                     odd++;
  57.                     if ((p.second * (p.second - 1)) / 2 == p.first) klika++;
  58.                 } else even++;
  59.             }
  60.         }
  61.         if (odd == 0) return 0;    
  62.         if (odd == 1) {
  63.             if (even == 0 && klika == 1) return -1;
  64.             return 1;
  65.         }
  66.         return odd;
  67.     }
  68. };
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