题目
牛奶生意正红红火火！
农夫约翰的牛奶加工厂内有 N 个加工站，编号为 1…N，以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，约翰在每条通道上安装了传送带。
不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！
所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，约翰认为事情可能还不算完全失败，只要至少还存在一个加工站 i 满足从其他每个加工站出发都可以到达加工站 i。
注意从其他任意一个加工站 j 前往加工站 i 可能会经过 i 和 j 之间的一些中间站点。
请帮助约翰求出是否存在这样的加工站 i。
题意
给出一个n个点，n-1条有向边，也就是说这是一颗树，问是否存在这样一个点：从其他任意一个点都能到这个点上，如果有多个请输出最小的那个。实际上最多就会有一个，限制的死死的，一棵树，有向。
思路
这个题目的方法很多很多，我至少看到了3种，我先说说我的，再来看看其他三种。
1）反向建边+dfs
一个点能被所有点走到，这说明反向建边的话他能够走到所有点，这样的话每次枚举这个点是否能走到所有点，这时间复杂度远比于正向枚举一个点，然后其他点走向它。
还有一个优化就是我们来计算入度出度，我们这个时候统计入度，我们只在入度为0的地方枚举，因为入度如果不为0，那么有其他的点能够走到该点，反向建边的时候就走不到了。
2）类似并查集
类似于并查集的方法，用数组来存它指向的，最后循环去找终点，统计终点个数，如果有个点的终点是n，那么就说明所有点都能够到这个点。
3）Floyd
基本思路：若i能到k，k能到j，则i一定能到达j。
利用Floyd传递闭包，求解所有点互相到达的情况，1表示可以，0表示不可以。
最后for循环1~n求出对于第i个点有多少个点能够到达它，如果等于n-1就直接输出这个i，退出循环即可。
4）O(n)
我们换种方法想一想，就单纯考虑出度的话，每次读入一个x,y代表有向边从点x指向点y，这个时候x有出度，这代表x必定不可能是我们所需要的点，二出度为0的点可能是我们所需要的，因为其他的点有可能都指向它。那么我们读完之后统计看看有多少个出度为0的点，如果cnt=1的话这代表着所有的点都能够到达这个点，因为这是一棵树，仔细想一想，只有一个出度为0的点，一共n个点n-1条边，是不是所有的点都只能到这里来呢？举不出反例的。
代码
1）反向建边+dfs
inline void dfs(int x)
{
vis[x]=1;
for (int i=head[x];i;i=edge[i].next)
dfs(edge[i].to);
}
inline void Case_Test()
{
cin>>n;
for (int i=1;i<n;i++)
{
cin>>x>>y;
add(y,x);
d[x]++;
}
for (int i=1;i<=n;i++)
{
if (d[i]) continue;
mem(vis,0);
dfs(i);
bool flag=false;
for (int j=1;j<=n;j++)
if (!vis[j]) flag=true;
if (flag) continue;
cout<<i;
return;
}
cout<<-1;
}
2）类似并查集
void parent(int a) //相当于找终点
{
while(ma[a]!=ma[ma[a]])
{
ma[a]=ma[ma[a]];
}
return ;
}
int main()
{
int n;
cin>>n;
for (int i = 1; i <= n; i ++ )ma[i]=i; //初始化 先让每个节点的终点是自己
map<int,int> root;
for (int i = 0; i < n; i ++ )
{
int a,b;
cin>>a>>b;
ma[a]=b;//覆盖没关系，覆盖肯定是不行的
}
for (int i = 1; i <= n; i ++ )parent(i);
for(auto it:ma)
{
root[it.second]++; //算终点
}
for(auto it:root)
{
if(it.second==n) //如果又n个点 能到符合条件 输出
{
cout<<it.first;
return 0;
}
}
cout<<"-1";
return 0;
//作者：deadpool
//链接：https://www.acwing.com/solution/content/90756/
}
3）Floyd
#include<bits/stdc++.h>
using namespace std;
int n, d[110][110], ans;
int main(){
scanf("%d", &n);
int u, v;
for (int i = 1; i < n; i++) scanf("%d%d", &u, &v), d[u][v] = 1;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) d[i][j] |= d[i][k] & d[k][j];//下方有解释
for (int i = 1; i <= n; i++) {
int cnt = 0;
for(int j = 1;j <= n; j++) if(d[j][i]) cnt++;
if(cnt == n - 1) {ans = i; break;}
}
if (ans) printf("%d", ans);
else puts("-1");
return 0;
}
//作者：封禁用户
//链接：https://www.acwing.com/solution/content/90857/
中间那个&的意思是且，这您应该知道吧，就是两个同时是1结果才是1，只要有一个是0结果就是0。
所以d[i][k] & d[k][j]的意思就是说i到k有一条路径并且k到j有一条路径，才返回1，否则返回值0。
然后前面还有一个d[i][j] |=，那个|是或运算，就是说如果两个值有一个是1返回就为1，如果都是1也返回1。然而如果是两个数都是0的话就返回0。
d[i][j] |= d[i][k] & d[k][j]这句可以转化成：d[i][j] = d[i][j] | (d[i][k] & d[k][j])，也就是说只要d[i][j]和d[i][k] & d[k][j]中有一个值为1，则d[i][j]赋值为1，否则为0。
用if语句的话会比较好理解一些
if(d[i][k] && d[k][j]) d[i][j] = 1;
比较直观
4）O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int d[N];
int main()
{
cin >> n;
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
cin >> a >> b;
d[a] ++ ;
}
int cnt = 0, id;
for (int i = 1; i <= n; i ++ )
if (!d[i])
{
cnt ++ ;
id = i;
}
if (cnt == 1) cout << id << endl;
else puts("-1");
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2561241/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。