मान लीजिए हमारे पास कुछ शीर्षों की डिग्री की सूची है। हमें जांचना है कि यह ग्राफ बनाती है या ट्री।
उदाहरण के लिए, यदि इनपुट deg = [2, 2, 3, 1, 1, 1] है, तो आउटपुट "Tree" होगा।
हल करने का तरीका
- vert := शीर्षों की संख्या
- deg_sum := सभी शीर्षों की डिग्री का योग
- यदि 2 × (vert - 1) == deg_sum, तो 'Tree' लौटाएं
- अन्यथा 'Graph' लौटाएं
यह ट्री की विशेषता पर आधारित है: n शीर्षों वाले ट्री में ठीक n-1 किनारे होते हैं, और डिग्री का योग 2(n-1) होता है।
उदाहरण कोड
def solve(deg):
vert = len(deg)
deg_sum = sum(deg)
if 2 * (vert - 1) == deg_sum:
return 'Tree'
return 'Graph'
deg = [2, 2, 3, 1, 1, 1]
print(solve(deg))
इनपुट
[2, 2, 3, 1, 1, 1]
आउटपुट
Tree
