1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int n, outDegree[N+1], farthestCut[N+1], ans;
struct Edge {
    int dst;
    Edge* next;
    Edge(int e, Edge* ne): dst(e), next(ne) {}
};
Edge* head[N+1];
inline void addEdge(int src, int dst) {
    auto p = new Edge(dst, head[src]->next);
    head[src]->next = p;
}
int findFarthestCut(int node) {
    if (farthestCut[node] != 0) return farthestCut[node];
    for(Edge* p = head[node] -> next; p; p = p -> next) {
        int mentor = p -> dst;
        if (mentor == 0) return farthestCut[node] = node;
        if (farthestCut[node] == 0) farthestCut[node] = findFarthestCut(mentor);
        else if (farthestCut[node] != findFarthestCut(mentor))
            return farthestCut[node] = node;
    }
    return farthestCut[node];
}
int main()
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX