Submission #13368080

---

Source Code Expand

/**
 *    author: Behradm
 *    Created: 18-05-2020 10:01:01
 *    In the Name of God
**/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+1;
vector<vector<int>> g;
int depth[maxn];
bool mark[maxn];

void Bfs(int u) {
	mark[u] = true;
	queue<int> q;
	q.push(u);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		mark[v] = true;
		//cerr << " [ " << v << " : " << depth[v] << " ] \n";
		for (int i = 0; i < (int) g[v].size(); i++) {
			int child = g[v][i];
			if (!mark[child]) {
				q.push(child);
				depth[child] = depth[v] + 1;
			}
		}
	}
	return;
}

pair<int, int> mini(int L, int R, vector<int> a) {
	if (R - L <= 1)
		return {a[L], depth[a[L]]};

	int mid = (L + R) / 2;
	auto v1 = mini(L, mid, a);
	auto v2 = mini(mid, R, a);
	if (v1.second <= v2.second) {
		return v1;
	} else {
		return v2;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	g.resize(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}

	depth[0] = 0;
	Bfs(0);

	/*cerr << '\n';
	for (int i = 0; i < n; i++)
		cerr << " [ " << i << " : " << depth[i] << " ] \n"; */

	/*for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			cout << "No\n";
			return 0;
		}
	}*/

	cout << "Yes\n";
	for (int u = 1; u < n; u++) {
		/*int res = g[u][0];
		for (int i = 0; i < (int) g[u].size(); i++) {
			int child = g[u][i];
			if (depth[child] <= depth[res]) 
				res = child;
		}*/

		cout << mini(0, (int) g[u].size(), g[u]).first + 1 << '\n';
	}
	return 0;
}

Submission Info

Judge Result