AtCoder Beginner Contest 168 D - .. (Double Dots)

题意:

有 个房间,在这些房间中两两连 次条边,问除了第一个房间,其他房间走到第一个房间的最短路径,输出这个房间所连的上一个房间,如果走不到,输出 .

AC代码;

const int N = 1e6 + 50;
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()
{
  sdd(n, m);
  rep(i, 1, m)
  {
    sdd(u, v);
    s[u].pb(v);
    s[v].pb(u);
  }
  bfs();
  rep(i, 1, n)
  {
    if (ans[i] == 0)
    {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  rep(i, 2, n)
    pd(ans[i]);
  return 0;
}