自动搬运

查看原文

来自洛谷，原作者为

	HasNoName 昭君出塞

搬运于2025-08-24 21:28:05，当前版本为作者最后更新于2024-01-21 13:58:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

问题

在一张 $N$ 个点有向图中，求编号最小的，所有点都能到的点。

没有所有点都能到的点输出 $-1$。

$(1\le N\le100)$。

方法

用一个数组统计每个点能被走到的数量。

对每个点进行搜索，把能到的点的能被走到的数量增加 $1$。

如果一个点能被走到的数量是 $N-1$ 则所有的点都能到。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
int w[N];//每个点能被走到的数量
bool vis[N];
struct T
{
    int to,ne;
}e[N];
int he[N],idx;
void add(int x,int y)//建图
{
    e[++idx].ne=he[x];
    e[idx].to=y;
    he[x]=idx;
}
void dfs(int x)//遍历
{
    vis[x]=1;//每个点只走一次
    for(int i=he[x];i;i=e[i].ne)//遍历每个临点
    {
        int y=e[i].to;
        if(!vis[y])//没被遍历过
        {
            w[y]++;
            dfs(y);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,x,y;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));//清空数组
        dfs(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(w[i]==n-1)
        {
            cout<<i<<'\n';
            return 0;
        }
    }
    cout<<"-1\n";//无解
    return 0;
}

记录。