Question:
What is the time complexity of finding the strongly connected components (SCC) of a directed graph using Tarjan’s algorithm?
टारजन के कलनविधि का उपयोग करके एक निर्देशित ग्राफ के दृढ़ता से जुड़े घटकों (SCC) को खोजने की समय जटिलता क्या है?
Options:
- \(O(V + E)\)
- \(O(V^2)\)
- \(O(V E)\)
- \(O(V \log V + E)\)
- \(O(V + E)\)
- \(O(V^2)\)
- \(O(V E)\)
- \(O(V \log V + E)\)
Correct Answer: a)
Explanation:
Tarjan’s strongly connected components algorithm performs a single DFS pass on the graph maintaining discovery times and low-link values using a stack, running in linear time \(O(V + E)\).
टारजन एल्गोरिदम केवल एक बार DFS ट्रैवर्सल करके स्टैक और लो-लिंक मानों द्वारा \(O(V + E)\) रैखिक समय में सभी SCC ज्ञात करता है।