Atcoder Beginner Contest 168 D - .. (Double Dots) (BFS)

题意:有\(n\)个房间,在这些房间中两两连\(m\)次条边,问除了第一个房间,其他房间走到第一个房间的最短路径,输出这个房间所连的上一个房间,如果走不到,输出\(no\).
题解:刚开始我写了一个dfs,结果竟然编译不了(段错误),稍加分析了一下,发现样例1中成环了,然后又在纸上画了画,发现可以用bfs来求解,直接上bfs的板子就行了.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int n,m;

int u,v;

int ans[N];

vector<int> s[N];

void bfs(){

    queue<int> q;

    q.push(1);

    ans[1]=1;

      while(!q.empty()){

          int tmp=q.front();

          q.pop();

          for(auto w:s[tmp]){

              if(ans[w]==0){

                  ans[w]=tmp;

                  q.push(w);

              }

          }

      }

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n>>m;

     for(int i=1;i<=m;++i){

         cin>>u>>v;

          s[u].pb(v);

          s[v].pb(u);

     }

     bfs();

     for(int i=1;i<=n;++i){

         if(ans[i]==0){

             puts("No");

             return 0;

         }

     }

     puts("Yes");

     for(int i=2;i<=n;++i) printf("%d\n",ans[i]);

    return 0;

}

巴特西

Atcoder Beginner Contest 168 D - .. (Double Dots) (BFS)

最新文章

热门文章