PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: naisheel, jalp1428
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
2554
PREREQUISITES:
BFS
PROBLEM:
Given an undirected graph, find the smallest non-negative integer K such that it’s possible to reach every other vertex from 1 in exactly K steps, or report that no such K exists.
EXPLANATION:
If we’re able to reach some vertex u via a walk of length x, we can also reach it via a walk of length x+2 — pick some edge incident to it and traverse it twice, once forwards and once backwards.
Suppose we knew for every vertex u the value \text{even}[u]: the shortest even-length walk from 1 to u.
Then, the smallest even K is just the largest of all the \text{even}[u] values, since for anything smaller we can go back-and-forth across an edge repeatedly till we reach the maximum.
Similarly, if we knew \text{odd}[u] for every u, the smallest odd K would be the maximum of them all.
The final answer is then just the minimum of the even and odd K we found.
Computing \text{even}[u] and \text{odd}[u] can be done with a straightforward modification of BFS.
Consider an auxiliary graph with 2N vertices: for each 1 \leq u \leq N, well have the vertices (u, 0) and (u, 1) denoting reaching u after an even or odd number of steps, respectively.
Traversing an edge always moves us from an even state to an odd state and vice versa.
So, for each original edge u\leftrightarrow v, add the edges (u, 0) \leftrightarrow (v, 1) and (u, 1) \leftrightarrow (v, 0) to this new graph.
Now, simply compute the distances from (1, 0) to every other vertex in this graph using BFS.
We obtain \text{even}[u] as \text{dist}[(u, 0)] and \text{odd}[u] as \text{dist}[(u, 1)], after which the minimum K is found as described at the start.
Note that in some cases it might be impossible to reach a certain vertex in an even and/or odd number of moves; make sure to consider this correctly to decide whether the answer is -1 or not.
The simplest way is to treat their distances as \infty, and if the final answer is \infty print -1 instead.
TIME COMPLEXITY
\mathcal{O}(N + M) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
// -------------------- Input Checker Start --------------------
// This function reads a long long, character by character, and returns it as a whole long long. It makes sure that it lies in the range [l, r], and the character after the long long is endd. l and r should be in [-1e18, 1e18].
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
if(!(fi == -1))
cerr << "- in between integer\n";
assert(fi == -1);
is_neg = true; // It's a negative integer
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0'; // fi is the first digit
cnt++;
// There shouldn't be leading zeroes. eg. "02" is not valid and assert will fail here.
if(!(fi != 0 || cnt == 1))
cerr << "Leading zeroes found\n";
assert(fi != 0 || cnt == 1);
// "-0" is invalid
if(!(fi != 0 || is_neg == false))
cerr << "-0 found\n";
assert(fi != 0 || is_neg == false);
// The maximum number of digits should be 19, and if it is 19 digits long, then the first digit should be a '1'.
if(!(!(cnt > 19 || (cnt == 19 && fi > 1))))
cerr << "Value greater than 1e18 found\n";
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
// We've reached the end, but the long long isn't in the right range.
cerr << "Constraint violated: Lower Bound = " << l << " Upper Bound = " << r << " Violating Value = " << x << '\n';
assert(false);
}
return x;
}
else if((g == ' ') && (endd == '\n'))
{
cerr << "Extra space found. It should instead have been a new line.\n";
assert(false);
}
else if((g == '\n') && (endd == ' '))
{
cerr << "A new line found where it should have been a space.\n";
assert(false);
}
else
{
cerr << "Something weird has happened.\n";
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
if(!(l <= cnt && cnt <= r))
cerr << "String length not within constraints\n";
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF()
{
char g = getchar();
if(g != EOF)
{
if(g == ' ')
cerr << "Extra space found where the file shold have ended\n";
if(g == '\n')
cerr << "Extra newline found where the file shold have ended\n";
else
cerr << "File didn't end where expected\n";
}
assert(g == EOF);
}
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
bool checkStringContents(string &s, char l, char r) {
for(char x: s) {
if (x < l || x > r) {
cerr << "String is not valid\n";
return false;
}
}
return true;
}
bool isStringBinary(string &s) {
return checkStringContents(s, '0', '1');
}
bool isStringLowerCase(string &s) {
return checkStringContents(s, 'a', 'z');
}
bool isStringUpperCase(string &s) {
return checkStringContents(s, 'A', 'Z');
}
bool isArrayDistinct(vector<int> a) {
sort(a.begin(), a.end());
for(int i = 1 ; i < a.size() ; ++i) {
if (a[i] == a[i-1])
return false;
}
return 1;
}
bool isPermutation(vector<int> &a) {
int n = a.size();
vector<int> done(n);
for(int x: a) {
if (x <= 0 || x > n || done[x-1]) {
cerr << "Not a valid permutation\n";
return false;
}
done[x-1]=1;
}
return true;
}
// -------------------- Input Checker End --------------------
void solve(){
int n,m;
n=readIntSp(1,1e5);
m=readIntLn(1,min((long long int)1e5,((n-1)*(long long int)n)/2));
vector<int> edge[n];
set<pair<int,int>> st;
for(int i=0;i<m;i++){
int u,v;
u=readIntSp(1,n);
v=readIntLn(1,n);
assert(u!=v);
st.insert({u,v});
st.insert({v,u});
edge[u-1].push_back(v-1);
edge[v-1].push_back(u-1);
}
assert(st.size()==2*m);
int cnt1=0,cnt2=0;
vector<vector<int>> vis(2,vector<int>(n,-1));
queue<pair<int,bool>> q;
vis[0][0]=0;
q.push({0,0});
while(!q.empty()){
int ind=q.front().first;
int dist=q.front().second;
q.pop();
for(auto chld: edge[ind]){
if(vis[1-dist][chld]==-1){
vis[1-dist][chld]=vis[dist][ind]+1;
q.push({chld,1-dist});
}
}
}
int ans0=0,ans1=0;
for(int i=0;i<n;i++){
if(vis[0][i]==-1)vis[0][i]=1e9;
if(vis[1][i]==-1)vis[1][i]=1e9;
ans0=max(ans0,vis[0][i]);
ans1=max(ans1,vis[1][i]);
}
int ans=min(ans0,ans1);
if(ans==1e9){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
}
int main(){
int tc;
tc=readIntLn(1,1000);
while(tc--){
solve();
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e3);
in.readEoln();
int sn = 0, sm = 0;
while (tt--) {
int n = in.readInt(1, 1e5);
in.readSpace();
int m = in.readInt(1, (int) min((long long) 1e5, n * 1LL * (n - 1) / 2));
in.readEoln();
sn += n;
sm += m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int x = in.readInt(1, n);
in.readSpace();
int y = in.readInt(1, n);
in.readEoln();
assert(x != y);
x--;
y--;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
vector<vector<int>> d(n, vector<int>(2, -1));
queue<pair<int, int>> que;
que.emplace(0, 0);
d[0][0] = 0;
while (!que.empty()) {
auto [v, p] = que.front();
que.pop();
for (int to : g[v]) {
if (d[to][p ^ 1] == -1) {
d[to][p ^ 1] = d[v][p] + 1;
que.emplace(to, p ^ 1);
}
}
}
const int inf = 1e9;
int ans = inf;
for (int i = 0; i < 2; i++) {
int t = 0;
for (int j = 0; j < n; j++) {
if (d[j][i] == -1) {
t = inf;
} else {
t = max(t, d[j][i]);
}
}
ans = min(ans, t);
}
if (ans == inf) {
ans = -1;
}
cout << ans << '\n';
}
assert(max(sn, sm) <= 1e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
adj = [ [] for _ in range(2*n)]
for i in range(m):
u, v = map(int, input().split())
u, v = u-1, v-1
adj[u].append(v+n)
adj[u+n].append(v)
adj[v].append(u+n)
adj[v+n].append(u)
dist = [10**9]*(2*n)
dist[0] = 0
queue = [0]
for u in queue:
for v in adj[u]:
if dist[v] > 1 + dist[u]:
dist[v] = 1 + dist[u]
queue.append(v)
ans = min(max(dist[:n]), max(dist[n:]))
if ans == 10**9: ans = -1
print(ans)