http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=117&problem=2870&mosmsg=Submission+received+with+ID+7753701

有向グラフが与えられる．何個の頂点を選べば，それらから出る有向道で頂点を被覆できますか．っていう問題．

入力サイズを見たかんじだと，線形ぐらいの計算量ならば良さそう．

で，パッと思いつくのが：

もし，グラフに閉路がない→簡単（入次数が0の点を数える）→強連結成分分解→閉路無し有向グラフ．

ただ，下のコードはシンプルとは言えない気がする．

もっと単純にできると思うが，もうすでに強連結成分分解のコードがあるのでそちらを利用してみた． 

//http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2870
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
typedef vector< vector<int> > AdjacencyList;
typedef vector<int>::const_iterator vit;

void visit(const AdjacencyList &g, int *label, stack<int> &stack, const int &u,
           int *num, int *low, int &index, int &size) {
  stack.push(u);
  low[u] = num[u] = ++index;
  for(vit v = g[u].begin(); v != g[u].end(); ++v) {
    if (label[*v] != -1) continue;
    if (num[*v] == 0) visit(g, label, stack, *v, num, low, index, size);
    low[u] = min(low[u], low[*v]);
  }

  if (num[u] == low[u]) {
    int v;
    do v = stack.top(), stack.pop(), label[v] = size;
    while (v != u);
    label[u] = size++;
  }
}

inline int count(const AdjacencyList &g) {
  const int n = g.size();
  int index = 0, size = 0, *num = new int[n], *low = new int[n], *label = new int[n];
  fill_n(num, n, 0), fill_n(low, n, 0), fill_n(label, n, -1);
  stack<int> stack;
  for (int i = 0; i < n; ++i)
    if (label[i] == -1) visit(g, label, stack, i, num, low, index, size);

  bool *root = new bool[size];
  fill_n(root, size, true);
  for (int i = 0; i < n; ++i) for(vit j = g[i].begin(); j != g[i].end(); ++j)
      if(label[i] != label[*j]) root[label[*j]] = false;

  int c = 0;
  for (int i = 0; i < size; ++i) if (root[i]) c++;
  return c;
}

int main() {
  int T;
  cin >> T;
  for (int _case = 1; _case <= T; ++_case) {
    int N, M;
    cin >> N >> M;
    vector< vector<int> > g(N);
    for (int i = 0; i < M; ++i) {
      int a, b;
      cin >> a >> b;
      g[--a].push_back(--b);
    }
    cout << "Case " << _case << ": " << count(g) << endl;
  }
}