結果
| 問題 |
No.1023 Cyclic Tour
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,909 bytes |
| コンパイル時間 | 774 ms |
| コンパイル使用メモリ | 81,300 KB |
| 実行使用メモリ | 14,208 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:58 |
| 合計ジャッジ時間 | 7,953 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 44 WA * 5 |
ソースコード
#include <iostream>
#include <vector>
#include <utility> // For std::pair
using namespace std;
// Global variables
// Adjacency list representation of the graph.
// Each element adj[u] is a vector of pairs {v, road_idx}, meaning there's a directed edge from u to v using road with index road_idx.
vector<vector<pair<int, int>>> adj;
// Stores the type of each road. road_type[i] = 1 if road i is bidirectional, 2 if unidirectional.
vector<int> road_type;
// Tracks the state of each vertex during DFS.
// 0: white (not visited yet)
// 1: gray (currently visiting, on the recursion stack)
// 2: black (finished visiting this node and all its descendants)
vector<int> visited;
/**
* @brief Performs Depth First Search (DFS) to detect cycles in the directed graph.
*
* This DFS implementation specifically handles the problem constraint:
* A cycle formed by immediately traversing a bidirectional road back and forth
* (e.g., u -> v -> u using the same bidirectional road i for both steps) is considered invalid.
* Such a traversal is disallowed because it uses the same "road" twice.
*
* @param u The current vertex being visited.
* @param incoming_road_idx The index of the road used to arrive at vertex u from its parent in the DFS tree.
* This is crucial for detecting and correctly handling the forbidden length-2 cycles.
* For the initial starting node of a DFS traversal, this value is -1.
* @return true if a valid cycle (according to the problem rules) is detected starting from or passing through u, false otherwise.
*/
bool dfs(int u, int incoming_road_idx) {
// Mark the current vertex u as gray, indicating it's currently being visited (on the recursion stack).
visited[u] = 1;
// Iterate through all outgoing edges from vertex u.
for (auto& edge : adj[u]) {
int v = edge.first; // The neighbor vertex connected by the current edge.
int current_road_idx = edge.second; // The index of the road corresponding to the edge (u, v).
// Check the state of the neighbor vertex v.
if (visited[v] == 1) { // Case 1: The edge leads to a gray node v.
// A gray node is currently on the recursion stack, meaning it's an ancestor of u in the DFS tree.
// This indicates that we have found a back edge, which completes a cycle.
// Now, we must check if this cycle is the specific forbidden type:
// A length-2 cycle u -> v -> u using the same bidirectional road for both steps.
// This condition holds if:
// 1. The current road (u -> v) `current_road_idx` is bidirectional (road_type == 1).
// 2. This road index `current_road_idx` is the same as the road index `incoming_road_idx`
// which was used to travel from v to u to reach the current node u.
// Check if road_type vector access is valid. road indices are 1..M. Vector indices are 0..M.
// Since current_road_idx comes from input (1 to M), access road_type[current_road_idx] is safe.
if (road_type[current_road_idx] == 1 && current_road_idx == incoming_road_idx) {
// This is exactly the forbidden cycle configuration.
// We should ignore this path and continue exploring other neighbors of u.
continue;
} else {
// We have found a valid cycle. This cycle is either:
// - Longer than length 2.
// - Length 2 (u -> v -> u), but valid because:
// - At least one of the edges (u, v) or (v, u) uses a unidirectional road.
// - Both edges use bidirectional roads, but they are different roads (different indices).
// In any case, a valid cycle exists. We can report true and terminate the search.
return true;
}
} else if (visited[v] == 0) { // Case 2: The edge leads to a white node v.
// A white node has not been visited yet in this DFS traversal.
// We explore this node recursively.
// We pass `current_road_idx` as the `incoming_road_idx` for the recursive call on v,
// because this is the road used to reach v from u.
if (dfs(v, current_road_idx)) {
// If the recursive call `dfs(v, ...)` returns true, it means a cycle was found
// somewhere down the path starting from v. We propagate this finding back up.
return true;
}
}
// Case 3: visited[v] == 2. The edge leads to a black node v.
// A black node has been fully explored previously (either in the current DFS traversal or a prior one).
// An edge to a black node signifies a cross edge or forward edge in the DFS tree structure.
// Such edges do not form *new* cycles involving the current path back to an ancestor (gray node).
// Therefore, we simply ignore this edge for the purpose of finding cycles involving the current path.
}
// After exploring all neighbors of u, if no cycle was found involving u through back edges,
// mark u as black, indicating that the visit to u and its descendants is complete.
visited[u] = 2;
// Return false, indicating no cycle was found originating from or passing through u along the paths explored from this DFS call.
return false;
}
int main() {
// Use faster I/O operations standard in competitive programming.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of cities (vertices)
int M; // Number of roads (original edges)
cin >> N >> M;
// Initialize data structures. We use size N+1 and M+1 to allow for 1-based indexing used in the problem statement.
adj.resize(N + 1);
road_type.resize(M + 1);
visited.resize(N + 1, 0); // Initialize all nodes as unvisited (white).
// Read road information and build the directed graph representation using an adjacency list.
for (int i = 1; i <= M; ++i) {
int u, v, c; // Read vertices u, v connected by road i, and road type c.
cin >> u >> v >> c;
road_type[i] = c; // Store the type of road i (1 for bidirectional, 2 for unidirectional).
if (c == 1) {
// If road i is bidirectional, it allows travel in both directions.
// Add a directed edge from u to v associated with road index i.
adj[u].push_back({v, i});
// Add a directed edge from v to u associated with the same road index i.
adj[v].push_back({u, i});
} else { // c == 2
// If road i is unidirectional, it allows travel only from u to v.
// Add a directed edge from u to v associated with road index i.
adj[u].push_back({v, i});
}
}
bool cycle_found = false;
// Iterate through all vertices from 1 to N.
// This loop ensures that we initiate DFS from each unvisited node,
// covering all potentially disconnected components of the graph.
for (int i = 1; i <= N; ++i) {
// If vertex i has not been visited yet (is white).
if (visited[i] == 0) {
// Start a new DFS traversal from vertex i.
// The initial call from the main loop doesn't have an incoming edge, so `incoming_road_idx` is -1.
if (dfs(i, -1)) {
// If the DFS call returns true, it means a valid cycle was found.
cycle_found = true;
// Since we only need to determine if *any* valid cycle exists, we can stop searching.
break;
}
}
}
// Print the final result based on whether a cycle was found.
if (cycle_found) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}