dfs简单水一下
查看原帖
dfs简单水一下
1197891
Mahongjian楼主2024/4/1 15:12

AC代码 就是判断节点被走过的次数是否为n-1

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int>p[110];//存图
int n,a[110];//每个点能被走到的数量  
bool vis[110];
void dfs(int x)
{
    vis[x] = 1;//走过置为1
    for(int y : p[x]){
        if(!vis[y]){
            a[y]++;//如果一个节点能被走n-1次,说明所有节点都可以访问到他
            dfs(y);
        }
    }
}
int main()
{
    cin>>n;
    int x,y;
    for(int i = 0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        p[x].push_back(y);
    }
    for(int i =1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));//想一想图的存储结构
        dfs(i);
    }
    for(int i = 1;i<=n;i++){
        if(a[i]==n-1){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}
```
2024/4/1 15:12
加载中...