SRM480 Div1 Medium

450

あるクライアントとあるサーバを直に結ぶケーブルにゲートを設置するかどうかは、
トポロジカル順序でそのクライアントとサーバの間にあるコンピュータのかに、
そのクライアントから到達可能で、そのサーバへ到達可能なコンピュータが１つでもあるかどうかによる。

class NetworkSecurity {
public:
  int secureNetwork(vector <string> C, vector <string> S)
  {
    const int node = C.size() + S[0].size();
    bool g[node][node];
    fill(&g[0][0], &g[node - 1][node], false);

    for (int i = 0; i < (int)C.size(); ++i) {
      for (int j = 0; j < (int)C.size(); ++j) {
        g[i][j] = C[i][j] == 'Y';
      }
    }
    for (int i = 0; i < (int)C.size(); ++i) {
      for (int j = 0; j < (int)S[0].size(); ++j) {
        g[i][j + C.size()] = S[i][j] == 'Y';
      }
    }

    bool h[node][node];
    copy(&g[0][0], &g[node - 1][node], &h[0][0]);
    for (int k = 0; k < (int)node; ++k) {
      for (int i = 0; i < (int)node; ++i) {
        for (int j = 0; j < (int)node; ++j) {
          h[i][j] = h[i][j] || (h[i][k] && h[k][j]);
        }
      }
    }

    vector<int> ord;
    vector<int> v;

    int deg[node];
    fill(deg, deg + node, 0);
    for (int i = 0; i < (int)node; ++i) {
      for (int j = 0; j < (int)node; ++j) {
        if (g[i][j]) ++deg[j];
      }
    }
    for (int i = 0; i < (int)node; ++i) {
      if (deg[i] == 0) v.push_back(i);
    }

    while (v.size()) {
      int n = v.back();
      v.pop_back();
      ord.push_back(n);
      for (int m = 0; m < node; ++m) {
        if (g[n][m]) {
          g[n][m] = false;
          if (--deg[m] == 0) v.push_back(m);
        }
      }
    }

    int o[node];
    for (int i = 0; i < (int)node; ++i) {
      o[ord[i]] = i;
    }

    int ret = 0;
    for (int c = 0; c < (int)C.size(); ++c) {
      for (int s = C.size(); s < (int)node; ++s) {
        if (h[c][s] && o[c] < o[s]) {
          bool flg = true;
          for (int i = o[c] + 1; i < o[s]; ++i) {
            if (h[c][ord[i]] && h[ord[i]][s] && h[ord[i]][s]) flg = false;
          }
          ret += flg;
        }
      }
    }
    return ret;
  }
};