UVa1263

UVa1263
グラフにする。
強連結成分分解して、頂点の入次数を見る。
強連結成分分解のコードは省略。だいたいスパソと同じ。

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;

    double x[n], y[n], a[n];
    for (int i = 0; i < n; ++i) {
      cin >> x[i] >> y[i] >> a[i];
    }

    Graph g(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (max(fabs(x[i] - x[j]), fabs(y[i] - y[j])) <= a[i] / 2.0) {
          g[i].push_back(Edge(i, j));
        }
      }
    }

    vector< vector<int> > scc = SCC(g);
    map<int, int> rename;
    for (int i = 0; i < scc.size(); ++i) {
      for (int j = 0; j < scc[i].size(); ++j) {
        rename[scc[i][j]] = i;
      }
    }

    int degree[scc.size()];
    fill(degree, degree + scc.size(), 0);

    for (int i = 0; i < g.size(); ++i) {
      for (int j = 0; j < g[i].size(); ++j) {
        int src = rename[g[i][j].src];
        int dst = rename[g[i][j].dst];
        if (src != dst) ++degree[dst];
      }
    }

    cout << count(degree, degree + scc.size(), 0) << endl;
  }
  return 0;
}