Link to a question: https://cses.fi/problemset/task/1666
Guide’s answer: https://usaco.guide/silver/dfs?lang=cpp
What is the time complexity of DFS:
- For Loop that trys every node -> O(N)
- DFS Loops through the adjacent list -> O(N)
- DFS Checks if the node has already been visited -> O(1)
So I think it’s O(N^2), but I feel that that’s pretty large so I’m assuming I made a mistake.
Please let me know!