萌新求助:DFS WA
查看原帖
萌新求助:DFS WA
236807
KaguyaH楼主2020/7/29 19:48

刚学搜索的彩笔求助 /kel

用的是 stl 里面的 stackqueue

知道可以改成递归。只是求助 stl 写法为什么会错()

# include <cctype>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>
# include <stack>
# include <vector>
using namespace std;

typedef short unsigned int hu;
typedef long unsigned int lu;
enum { N = (const lu)1e5 };

const class IOstream {
public:
	inline const IOstream operator>>(lu&) const;
	inline const IOstream operator<<(lu) const;
	inline const IOstream operator<<(const char) const;
} io;

static lu n, m;
static vector<lu> o[N + 1];
static bool v[N + 1];

signed int main() {
	io >> n >> m;
	for (register lu i(0); i < m; ++i) {
		static lu x, y; io >> x >> y;
		o[x].push_back(y);
	}
	for (register lu i(1); i <= n; ++i) sort(o[i].begin(), o[i].end());
	{
		stack<lu> t; t.push(1), v[1] = true;
		while (not t.empty()) {
			const lu u(t.top()); t.pop(); io << u;
			for (lu i(o[u].size() - 1); i < o[u].size(); --i)
				if (not v[o[u][i]]) t.push(o[u][i]), v[o[u][i]] = true;
		}
		io << '\n', memset(v, 0, sizeof v);
	}
	{
		queue<lu> t; t.push(1), v[1] = true;
		while (not t.empty()) {
			const lu u(t.front()); t.pop(); io << u;
			for (lu i(0); i < o[u].size(); ++i) if (not v[o[u][i]]) t.push(o[u][i]), v[o[u][i]] = true;
		}
		io << '\n', memset(v, 0, sizeof v);
	}
	return 0;
}

inline const IOstream IOstream::operator>>(lu& a) const {
	char t; while (isspace(t = getchar())); a = 0; while (a = a * 10 + (t - '0'), isdigit(t = getchar()));
	return *this;
}
inline const IOstream IOstream::operator<<(lu a) const {
	char s[6]; hu l(0); while (s[l++] = a % 10 + '0', a /= 10); while (l) putchar(s[--l]); putchar(' ');
	return *this;
}
inline const IOstream IOstream::operator<<(const char a) const { putchar(a); return *this; }
2020/7/29 19:48
加载中...