（これは最近完了したプログラミングコンテストから派生しています）
N個のノードとN-1個のエッジを持つ連結グラフであるGが与えられます。
（これは、Gがツリーを形成することを意味することに注意してください。）
Gの各エッジが方向付けられます。（必ずしもルートに対して上向きである必要はありません）
Gの各頂点vについて、他のすべての頂点wからvへの有向パスが存在するように0個以上のエッジを反転することができます。これを実現するためのエッジ反転の可能な最小数をf（v）とします。
どの線形または対数線形アルゴリズムによって、全体として最小のf（v）（それらの頂点のf（v）の値を含む）を持つ頂点のサブセットを決定できますか？
たとえば、次のエッジを持つ4つの頂点グラフについて考えてみます。
A<--B
C<--B
D<--B
f（A）= 2、f（B）= 3、f（C）= 2およびf（D）=2..の値
..したがって、必要な出力は{A、C、D}および2です。
（最小のf（v）を持つ頂点のf（v）のみを計算する必要があることに注意してください-すべてではありません）
コード：
後世のために、ここに解決策のコードがあります：
int main()
{
struct Edge
{
bool fwd;
int dest;
};
int n;
cin >> n;
vector<vector<Edge>> V(n+1);
rep(i, n-1)
{
int src, dest;
scanf("%d %d", &src, &dest);
V[src].push_back(Edge{true, dest});
V[dest].push_back(Edge{false, src});
}
vector<int> F(n+1, -1);
vector<bool> done(n+1, false);
vector<int> todo;
todo.push_back(1);
done[1] = true;
F[1] = 0;
while (!todo.empty())
{
int next = todo.back();
todo.pop_back();
for (Edge e : V[next])
{
if (done[e.dest])
continue;
if (!e.fwd)
F[1]++;
done[e.dest] = true;
todo.push_back(e.dest);
}
}
todo.push_back(1);
while (!todo.empty())
{
int next = todo.back();
todo.pop_back();
for (Edge e : V[next])
{
if (F[e.dest] != -1)
continue;
if (e.fwd)
F[e.dest] = F[next] + 1;
else
F[e.dest] = F[next] - 1;
todo.push_back(e.dest);
}
}
int minf = INT_MAX;
rep(i,1,n)
chmin(minf, F[i]);
cout << minf << endl;
rep(i,1,n)
if (F[i] == minf)
cout << i << " ";
cout << endl;
}