結果
| 問題 |
No.2674 k-Walk on Bipartite
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:07:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 70 ms / 2,000 ms |
| コード長 | 9,912 bytes |
| コンパイル時間 | 859 ms |
| コンパイル使用メモリ | 84,060 KB |
| 実行使用メモリ | 14,424 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:10 |
| 合計ジャッジ時間 | 3,213 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
// Using long long for k is important due to its large potential value up to 10^9.
// Using long long for distance comparison with k. Distance values themselves would fit in int if N <= 2*10^9.
// Using -1LL to represent infinity/unreachable distance, ensures type compatibility with long long.
const long long INF = -1LL;
int main() {
// Faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of vertices
int M; // Number of edges in the given subset F
std::cin >> N >> M;
long long s_ll, t_ll; // Use long long temporarily to read vertex IDs
long long k; // Walk length
std::cin >> s_ll >> t_ll >> k;
// Cast vertex IDs to int, as they are used as indices and guaranteed to be within [1, N].
int s = static_cast<int>(s_ll);
int t = static_cast<int>(t_ll);
// Adjacency list representation for the given graph H=(V, F)
std::vector<std::vector<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
int u, v;
std::cin >> u >> v;
// Add edges to adjacency list. Since it's an undirected graph, add edge in both directions.
// Assuming problem statement constraints 1 <= Ai < Bi <= N hold.
adj[u].push_back(v);
adj[v].push_back(u);
}
// Handle the case where the given edge set F is empty (M=0) separately.
// In this case, H has no edges. Any bipartite supergraph G can be formed.
if (M == 0) {
if (N == 1) {
// The graph has only one vertex. s=1, t=1. Since k>=1, we need to take at least one step.
// With no edges, no movement is possible. A walk of length k>=1 doesn't exist.
std::cout << "No" << std::endl;
} else { // N >= 2
if (s == t) {
// A walk from s to s in any bipartite graph must have even length.
if (k % 2 != 0) {
// k is odd. Impossible in any bipartite graph.
std::cout << "No" << std::endl;
} else { // k is even and k >= 2 (since k>=1 is a problem constraint).
// In H (no edges), no walk exists.
// Can we add edges to form a bipartite graph G where a walk exists? Yes, if N>=2.
// We can form a complete bipartite graph K_{V1, V2} with non-empty V1, V2.
// E.g., partition V into {s} and V\{s}. Since N>=2, V\{s} is non-empty.
// In the complete bipartite graph K_{{s}, V\{s}}, we can take a walk s -> neighbor -> s.
// This has length 2. We can extend it to any even length k >= 2 by repeating steps.
// Since H has no walk, but some G does, the answer is Unknown.
std::cout << "Unknown" << std::endl;
}
} else { // s != t
// Need to determine if a walk s->t of length k is possible in some G.
// This depends on the parity of k and how s, t are placed in the bipartition.
if (N == 2) {
// The only vertices are s and t. The only possible bipartite graph G with edges is the single edge (s, t).
// This graph G has partition {s}, {t}. s and t are in different parts.
// A walk s->t exists if and only if k is odd.
if (k % 2 == 0) { // k is even. Need s, t in same partition. Impossible in G.
std::cout << "No" << std::endl;
} else { // k is odd. Need s, t in different partitions. Possible in G.
// H has no walk. G has walk. So it's Unknown.
std::cout << "Unknown" << std::endl;
}
} else { // N >= 3
// We can always construct a complete bipartite graph G = K_{V1, V2} where a walk s->t of length k exists.
// If k is odd, we need s and t in different parts. The partition V1={s}, V2=V\{s} works. G has the walk.
// If k is even, we need s and t in the same part. The partition V1={s, t}, V2=V\{s, t} works because N>=3 implies V2 is non-empty. G has the walk.
// Since H has no walk, but some G potentially has a walk, the answer is Unknown.
std::cout << "Unknown" << std::endl;
}
}
}
return 0; // Exit after handling M=0 case
}
// Case M > 0
// Compute connected components and determine the bipartition (parities) for each component using BFS.
std::vector<int> comp(N + 1, 0); // Stores component ID for each vertex. 0 means unvisited.
std::vector<int> parity(N + 1, -1); // Stores parity (0 or 1) within component. -1 means unassigned.
int curr_comp = 0; // Counter for component IDs.
// Iterate through all vertices to find all connected components.
for (int v = 1; v <= N; ++v) {
if (comp[v] == 0) { // If vertex v hasn't been visited yet, it starts a new component.
curr_comp++;
std::queue<int> q_comp; // Queue for BFS for this component.
q_comp.push(v);
comp[v] = curr_comp;
parity[v] = 0; // Assign parity 0 to the starting vertex of the component.
// Perform BFS to find all vertices in the component and assign parities.
while (!q_comp.empty()) {
int u = q_comp.front();
q_comp.pop();
for (int neighbor : adj[u]) {
if (comp[neighbor] == 0) { // If neighbor is unvisited.
comp[neighbor] = curr_comp; // Assign component ID.
parity[neighbor] = 1 - parity[u]; // Assign opposite parity.
q_comp.push(neighbor);
}
// The problem guarantees H is bipartite, so no need to check for conflicts.
}
}
}
}
// Check if s and t belong to different connected components in H.
if (comp[s] != comp[t]) {
// If s and t are in different components in H, there is no path between them in H.
// However, edges could potentially be added between components to form a larger bipartite graph G.
// It's always possible to construct such a G where s and t are connected and satisfy the parity requirement for length k walk.
// Example: Construct a K_{V1, V2} based on the H components' partitions.
// Since H has no path, but some G might have a path, the outcome is uncertain.
std::cout << "Unknown" << std::endl;
return 0;
}
// s and t are in the same connected component in H.
// Check the necessary parity condition for a walk of length k.
// A walk from s to t of length k exists in a bipartite graph only if parity(t) == (parity(s) + k) % 2.
bool k_parity_odd = (k % 2 != 0);
bool st_parity_diff = (parity[s] != parity[t]);
// The condition parity(t) == (parity(s) + k) % 2 is equivalent to (parity[s] != parity[t]) == (k % 2 != 0).
// i.e., s, t have different parities if and only if k is odd.
if (st_parity_diff != k_parity_odd) {
// If the parity condition fails, no walk of length k from s to t can exist in ANY bipartite graph G containing H.
std::cout << "No" << std::endl;
return 0;
}
// The parity condition holds. Now we check if a walk of length k exists in H itself.
// In a connected bipartite graph, a walk of length k exists from s to t if and only if
// the shortest distance d(s, t) satisfies d(s, t) <= k and d(s, t) % 2 == k % 2.
// The parity match d(s, t) % 2 == k % 2 is already guaranteed because we passed the parity check above, assuming t is reachable.
// So we only need to check if d(s, t) <= k. We compute d(s, t) using BFS.
std::vector<long long> dist(N + 1, INF); // Stores shortest distance from s. Initialize with INF.
std::queue<int> q_bfs; // Queue for BFS for shortest path distance calculation.
dist[s] = 0; // Distance from s to s is 0.
q_bfs.push(s);
long long d_st = INF; // Variable to store the shortest distance d(s, t).
// Perform BFS starting from s to find the shortest path to t.
while (!q_bfs.empty()) {
int u = q_bfs.front();
q_bfs.pop();
if (u == t) {
d_st = dist[t]; // Found t, store the distance.
break; // Shortest path found, can stop BFS.
}
// Explore neighbors of u.
for (int neighbor : adj[u]) {
// Only explore neighbors that haven't been visited yet (dist == INF).
if (dist[neighbor] == INF) {
dist[neighbor] = dist[u] + 1; // Update distance.
q_bfs.push(neighbor); // Add neighbor to queue.
}
}
}
// Final decision based on reachability within k steps in H.
if (d_st != INF && d_st <= k) {
// If t is reachable from s in H (d_st != INF), and the shortest path distance d_st <= k.
// Since the parity condition also holds, a walk of length k exists in H.
// If a walk exists in H, it exists in any supergraph G. Therefore, the answer is Yes.
std::cout << "Yes" << std::endl;
} else {
// If t is unreachable in H (d_st == INF) or the shortest path is longer than k (d_st > k).
// A walk of length k does not exist in H.
// However, the parity condition holds. This implies that in a complete bipartite graph K_{V1, V2}
// built on a compatible partition, a walk of length k would exist.
// Since the walk doesn't exist in H, but could exist in some potential supergraph G, the answer is Unknown.
std::cout << "Unknown" << std::endl;
}
return 0;
}