#include <iostream>
#include <vector>
#include <queue>
#include <assert.h>
using namespace std;
vector<vector<int>> EdgeToNeiBo(int n,const vector<vector<int>>& edges)
{
vector<vector<int>> vNeiB(n);
for (const auto& v : edges)
{
vNeiB[v[0]].emplace_back(v[1]);
vNeiB[v[1]].emplace_back(v[0]);
}
return vNeiB;
}
class CBFS1
{
public:
CBFS1(vector<vector<int>>& vNeiB, int s)
{
m_vDis.assign(vNeiB.size(), -1);
m_vDis[s] = 0;
vector<queue<int>> ques(vNeiB.size());
ques[0].emplace(s);
for (int i = 1; (i < ques.size()) && ques[i - 1].size(); i++)
{
auto& pre = ques[i - 1];
while (pre.size())
{
const int cur = pre.front();
pre.pop();
for (const auto next : vNeiB[cur])
{
if (-1 != m_vDis[next])
{
continue;
}
m_vDis[next] = m_vDis[cur] + 1;
ques[i].emplace(next);
}
}
}
}
public:
vector<int> m_vDis;
};
class CBFS2
{
public:
CBFS2(vector<vector<int>>& vNeiB, int s)
{
m_vDis.assign(vNeiB.size(), -1);
m_vDis[s] = 0;
queue<int> pre;
pre.emplace(s);
for (int i = 1; pre.size(); i++)
{
queue<int> dp;
while (pre.size())
{
const int cur = pre.front();
pre.pop();
for (const auto next : vNeiB[cur])
{
if (-1 != m_vDis[next])
{
continue;
}
m_vDis[next] = m_vDis[cur] + 1;
dp.emplace(next);
}
}
dp.swap(pre);
}
}
public:
vector<int> m_vDis;
};
class CBFS3
{
public:
CBFS3(vector<vector<int>>& vNeiB, int s)
{
m_vDis.assign(vNeiB.size(), -1);
m_vDis[s] = 0;
queue<int> que;
que.emplace(s);
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto next : vNeiB[cur])
{
if (-1 != m_vDis[next])
{
continue;
}
m_vDis[next] = m_vDis[cur] + 1;
que.emplace(next);
}
}
}
public:
vector<int> m_vDis;
};
#define CBFS CBFS1
class CDebugBFS : public CBFS
{
public:
using CBFS::CBFS1;
void Assert(const vector<int>& vDis)
{
for (int i = 0; i < vDis.size(); i++)
{
assert(vDis[i] == m_vDis[i]);
}
}
};
struct CDebugParam
{
int n;
vector<vector<int>> edges;
int s;
vector<int> dis;//答案
};
int main()
{
vector<CDebugParam> params = { {1,{},0,{0}},{2,{},0,{0,-1}},
{6,{{0,1},{1,2},{1,3},{2,4},{4,5},{3,5}},0,{0,1,2,2,3,3} }
};
for (const auto& par : params)
{
auto vNeiB = EdgeToNeiBo(par.n, par.edges);
CDebugBFS bfs(vNeiB,par.s);
bfs.Assert(par.dis);
}
}
