UVa1229 Sub-dictionary

問題

https://uva.onlinejudge.org/external/12/1229.pdf
個の単語が載っている辞書がある。すべての単語を理解したい。
サンプルの場合、

5
aue oizer piqoi oizer
doy oizer hweqlo hweqlo
hweqlo piqoi aue
oizer piqoi
piqoi aue aue
0

となっていて、「aueを理解するためにはoizer, piqoiの2つの単語を理解する必要がある」という感じになっている。

もしも、はじめに "aue, oizer, piqoi" が分かっていれば、辞書のすべての単語を理解することが出来るようになる。
はじめに辞書を使わずに理解する必要のある単語を列挙せよ。

ただし、はじめに辞書を使わずに理解する単語の集合には条件がある（この条件は結構トリッキーで、誤解法を生みやすいと感じた）
サンプルの場合、初期でpiqoiのみを理解することは出来ない。もし初期でpiqoiを理解したいのならば、初期で覚える単語の集合にaueも含まれている必要がある。
同様に、初期でaueを理解するためにはoizer, piqoiもまた、初期で覚える単語の集合に含まれている必要がある。

解法

入力されたグラフをSCCする。
頂点に単語が2つ以上含まれていれば、それらの単語は必ず初期で理解していなければならない（自明）
それらの単語に加えて、先ほどの条件により、それらの単語を理解するために必要な単語も追加しなければらない。
なので、条件が満たされるまで追加を繰り返さなければならない。つまり、2つ以上の単語を持つ頂点に至るパスに含まれる単語をすべて覚える必要がある。これは元のグラフの逆辺で構成されたグラフを作り、2つ以上の単語を持つ頂点からDFSすることで求めることが出来る。

namespace graph {

// Verified: UVa247
struct tarjanSCC {

  int const Unvisited = -1;

  typedef vector<vector<int>> graph;

  graph* g;
  int V;
  int dfsNumberCounter;
  vector<int> dfsNum, dfsLow, visited;
  stack<int> S;
  vector<vector<int>> comp;
  vector<int> compNum;

  void dfs(int u) {
    dfsLow[u] = dfsNum[u] = dfsNumberCounter ++;
    S.push(u);
    visited[u] = 1;
    for(auto v: (*g)[u]) {
      if(dfsNum[v] == Unvisited)
        dfs(v);
      if(visited[v])
        dfsLow[u] = min(dfsLow[u], dfsLow[v]);
    }

    if(dfsLow[u] == dfsNum[u]) {
      comp.resize(comp.size() + 1);
      while(1) {
        int v = S.top(); S.pop(); visited[v] = 0;
        comp.back().push_back(v);
        compNum[v] = comp.size() - 1;
        if(u == v) break;
      }
    }
  }

  tarjanSCC(graph* g) {
    this->g = g;
    V = g->size();
    dfsNum.assign(V, Unvisited);
    dfsLow.assign(V, 0);
    visited.assign(V, 0);
    compNum.assign(V, -1);
    dfsNumberCounter = 0;
    for(int i=0; i<V; i++) {
      if(dfsNum[i] == Unvisited) {
        dfs(i);
      }
    }
  }

};

}

void add_to_map(map<string, int>& mp, map<int, string>& umap, string& s, int& v) {
  if(mp.find(s) == mp.end()) {
    mp[s] = v;
    umap[v] = s;
    v++;
  }
}

template<class T> ostream& operator << (ostream& ost, vector<T> const& v) { ost << "["; rep(i, v.size()) { if(i) ost << ", "; ost << v[i]; } ost << "]"; return ost; }

void dfs(graph::tarjanSCC::graph& g, int u, vector<bool>& vis) {
  if(vis[u]) return;
  vis[u] = 1;
  for(int v: g[u]) {
    dfs(g, v, vis);
  }
}

int main() {

  for(int N; cin >> N && N;) {
    cin.ignore();
    map<string, int> mp;
    map<int, string> umap;
    int v = 0;
    graph::tarjanSCC::graph g(N);
    graph::tarjanSCC::graph revG(N);
    rep(i, N) {
      string s; getline(cin, s);
      stringstream ss(s);
      string t; ss >> t; add_to_map(mp, umap, t, v);
      while(ss >> s) {
        add_to_map(mp, umap, s, v);
        g[mp[s]].push_back(mp[t]);
        revG[mp[t]].push_back(mp[s]);
      }
    }

    graph::tarjanSCC scc(&g);

    vector<string> ans;
    vector<bool> vis(N);

    for(auto v: scc.comp) {
      if(v.size() > 1) {
        for(auto e: v) {
          dfs(revG, e, vis);
        }
      }
    }

    rep(i, N) {
      if(vis[i]) ans.push_back(umap[i]);
    }

    sort(all(ans));

    cout << ans.size() << endl;

    rep(i, ans.size()) {
      if(i) cout << " ";
      cout << ans[i];
    }
    cout << endl;

  }
  
  return 0;
}