G - Genealogy Gym - 100519G（有环图拓扑排序）

本文主要是介绍G - Genealogy Gym - 100519G（有环图拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

As you may know, the dates in historical documents and descriptions can be given rather inaccurately. It often occurs that in a description of a historic event, the closest thing to a date is something like “In the times of Isaac, the son of Abraham”.

The professor Mofenko who is an admirer of alternative history wants to determine the maximum length of the chain of people from father to son that can be composed of people from a given list. With the help of this information, he can invent a lot of amusing alternative histories that are irrefutable by documents.

For each person in the list, his family name, his first name and the first name of his father are given. The family names of a father and his son are always equal. By a happy coincidence, it turned out that all first names of all people in the list are distinct.

Input
The first line of input contains an integer N: the number of the descriptions of people (1 ≤ N ≤ 105).

The next N lines contain the description of a man in the following format: the family name, the first name, the words “son of” and the first name of his father.

All first names and family names start with a capital English letter, and all letters except the first one are lowercase English letters. Consecutive words are separated by a single space character. The length of each first name and each family name is not greater than 10.

Note that it is possible that some person in the list has father outside of the list, but this father shouldn’t be included in the chain. It is guaranteed that all N first names of people in the list are pairwise distinct; however, this restriction may not affect first names of people outside of the list.

Output
Output a single integer: the number of people in the longest chain.

Examples
Input
7
Bible Isaak son of Abraham
Bible Jacob son of Isaak
Ivanov Ivan son of Petr
Ivanov Protopop son of Vasiliy
Ivanov Vasiliy son of Ivan
Ivanov Petr son of Vasiliy
Bible Judah son of Jacob
Output
4
Input
3
Ivanov Ivan son of Petr
Ivanov Petr son of Vasiliy
Petrov Vasiliy son of Ivan
Output
2
Note
In the first example, the longest chain is: Ivanov Petr, Ivanov Ivan, Ivanov Vasiliy, Ivanov Protopop.
In the second example, the longest chain is: Ivanov Petr, Ivanov Ivan.

两场比赛都出了topo，都没写出来。。。
题意：
有 $n$ 个人，给出每个人的父亲。每个人只有一个父亲，可以有多个儿子。且图有环，求图上最长链。

思路：
这个环看的我很迷，当然这不是重点。假设你按照儿子连接父亲建图，那么对于每一个环只可能有入度不可能有出度。那么环相当于缩点了。你不考虑环，那就变成了一个森林。topo排序取更新每个节点为结尾的最长链，最后特判环。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cmath>using namespace std;
typedef long long ll;const ll maxn = 1e5 + 7;int deg[maxn],ans,vis[maxn],f[maxn];
map<pair<string,string>,int>mp;
int n;struct Node {string family;string name;string father;
}a[maxn];int head[maxn],nex[maxn],to[maxn],tot;void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void topo() {queue<int>q;for(int i = 1;i <= n;i++) {if(deg[i] == 0) {q.push(i);}}while(!q.empty()) {int x = q.front();q.pop();vis[x] = 1;for(int i = head[x];i;i = nex[i]) {int y = to[i];f[y] = f[x] + 1;ans = max(ans,f[y]);deg[y]--;if(deg[y] == 0) {q.push(y);}}}
}int num;
int dfs(int x) {int cnt = 1;num = max(num,f[x]);for(int i = head[x];i;i = nex[i]) {int v = to[i];if(vis[v]) continue;vis[v] = 1;cnt += dfs(v);}return cnt;
}int main() {cin >> n;for(int i = 1;i <= n;i++) {f[i] = 1;string s1,s2,s3,s4,s5;cin >> s1 >> s2 >> s3 >> s4 >> s5;mp[{s1,s2}] = i;a[i].family = s1;a[i].name = s2;a[i].father = s5;}ans = 1;for(int i = 1;i <= n;i++) {string s1 = a[i].family,s2 = a[i].name,s3 = a[i].father;int num1 = mp[{s1,s3}]; //老子int num2 = mp[{s1,s2}]; //儿子if(num1 == 0) continue;add(num2,num1);
//        printf("%d %d\n",num1,num2);deg[num1]++;}topo();for(int i = 1;i <= n;i++) {if(!vis[i]) {num = 0;int circle = dfs(i) - 1;ans = max(ans,circle + num - 1);}}printf("%d\n",ans);return 0;
}