\(AcWing\) \(1471\). 牛奶工厂
一、题目描述
牛奶生意正红红火火！
农夫约翰的牛奶加工厂内有 \(N\) 个加工站，编号为 \(1…N\)，以及 \(N−1\) 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，约翰在每条通道上安装了传送带。
不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！
所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，约翰认为事情可能还不算完全失败，只要至少还存在一个加工站 \(i\) 满足从其他每个加工站出发都可以到达加工站 \(i\)。
注意从其他任意一个加工站 \(j\) 前往加工站 \(i\) 可能会经过 \(i\) 和 \(j\) 之间的一些中间站点。
请帮助约翰求出是否存在这样的加工站 \(i\)。
输入格式
输入的第一行包含一个整数 \(N\)，为加工站的数量。
以下 \(N−1\)行每行包含两个空格分隔的整数 \(a_i\) 和 \(b_i\)，满足 \(1≤a_i,b_i≤N\) 以及 \(a_i≠b_i\)。
这表示有一条从加工站 \(a_i\) 向加工站 \(b_i\) 移动的传送带，仅允许沿从 \(a_i\) 到 \(b_i\) 的方向移动。
输出格式
如果存在加工站 \(i\) 满足可以从任意其他加工站出发都可以到达加工站 \(i\)，输出最小的满足条件的 \(i\)。
否则，输出 \(−1\)。
数据范围
\(1≤N≤100\)
输入样例：
3
1 2
3 2
输出样例：
2
二、题目解析
传递闭包 问题就是一类具有传递性的问题。
按人话来说就是: 在一个元素集里，对你说一堆：某两个元素之间有关系。然后问你这些元素中一共有多少个元素有关系。
传递闭包概念的重点:
这个关系必须是二元的，也就是说，其他的多元关系也一定要可以分解为几个二元关系的累积。
传递闭包问题的转化和解决
可以将传递闭包问题转化为图论问题。
把元素变成一个点，有关系就连一条边。
最后用\(Floyd\)算法解决两点之间的连通关系。（任意两点）
基本思路：若\(i\)能到\(k\)，\(k\)能到\(j\)，则\(i\)一定能到达\(j\)。
利用\(Floyd\)传递闭包，求解所有点互相到达的情况，\(1\)表示可以，\(0\)表示不可以。
最后\(for\)循环\(1\)~\(n\)求出对于第\(i\)个点有多少个点能够到达它，如果等于\(n-1\)就直接输出这个\(i\)，退出循环即可。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, d[N][N], 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;
// Floyd求传递闭包
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++; //有多少个点可以到达i点
if (cnt == n - 1) {
ans = i;
break;
}
}
if (ans)
printf("%d", ans);
else
puts("-1");
return 0;
}