-
Notifications
You must be signed in to change notification settings - Fork 35
Closed
Labels
category: graphGraph algorithm problemsGraph algorithm problemscategory: mathematicsMathematical problemsMathematical problemsenhancementNew feature or requestNew feature or requestgood first issueGood for newcomersGood for newcomershacktoberfestIssues/PRs for Hacktoberfest participationIssues/PRs for Hacktoberfest participationhacktoberfest_2025Hacktoberfest 2025 specific contributionsHacktoberfest 2025 specific contributionshelp wantedExtra attention is neededExtra attention is needed
Description
🎯 Problem Information
- Problem Name: Round Trip
- CSES Link: https://cses.fi/problemset/task/1669/
- Category: Graph Algorithms
- Estimated Difficulty: Medium
📋 Problem Description
Byteland has n cities and m roads. The task is to find any cycle (round trip) in the undirected graph — a path that starts and ends at the same city, passing through at least two other distinct cities.
If no cycle exists, print IMPOSSIBLE.
💡 Proposed Approach
- Use DFS to detect a cycle in the undirected graph.
- Track parent nodes to reconstruct the cycle path when found.
- If a visited node (other than the parent) is encountered, we found a cycle.
- Once detected, backtrack using the parent array to print the cycle.
Time Complexity: O(n + m)
Space Complexity: O(n + m)
📝 Implementation Notes
Any special considerations or optimizations needed:
- Requires fast I/O
- Needs modular arithmetic
- Large input constraints
- Edge cases to consider
🏷️ Labels
Please add appropriate labels:
-
hacktoberfest(if contributing during Hacktoberfest) -
good first issue(if suitable for beginners) -
help wanted(if you need assistance)
👤 Assignee
- I would like to work on this issue
- I'm available for guidance/review
📎 Additional Context
Tested on the sample input and several custom cases — works for both connected and disconnected graphs.
Metadata
Metadata
Assignees
Labels
category: graphGraph algorithm problemsGraph algorithm problemscategory: mathematicsMathematical problemsMathematical problemsenhancementNew feature or requestNew feature or requestgood first issueGood for newcomersGood for newcomershacktoberfestIssues/PRs for Hacktoberfest participationIssues/PRs for Hacktoberfest participationhacktoberfest_2025Hacktoberfest 2025 specific contributionsHacktoberfest 2025 specific contributionshelp wantedExtra attention is neededExtra attention is needed