【图的遍历】AcWing1471.牛奶工厂USACO 2019 US Open Contest Bronze

题目

牛奶生意正红红火火！
农夫约翰的牛奶加工厂内有 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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。