मेरा तर्क SPOJ TOPOSORT के लिए सही तरीके से क्यों काम नहीं कर रहा है?

Question

भी समस्या http://www.spoj.com/problems/TOPOSORT/ है उत्पादन प्रारूप विशेष रूप से महत्वपूर्ण है के रूप में:

Print "Sandro fails." if Sandro cannot complete all his duties on the list. 
If there is a solution print the correct ordering, 
the jobs to be done separated by a whitespace. 
If there are multiple solutions print the one, whose first number is smallest, 
if there are still multiple solutions, print the one whose second number is smallest, and so on. 

क्या मैं कर रहा हूँ बस किनारों यानी नौकरी बी से पहले काम एक खत्म करता है, तो पीछे से DFS कर रही है, वहाँ एक निर्देशित किनारे से है बी से ए। मैं बनाई गई आसन्नता सूची को सॉर्ट करके ऑर्डर को बनाए रख रहा हूं और उन नोड्स को संग्रहीत कर रहा हूं जिनके पास अलग-अलग बाधाएं नहीं हैं ताकि उन्हें बाद में सही क्रम में प्रिंट किया जा सके। दो फ्लैग सरणी उपयोग की जाती हैं, एक खोजी गई नोड को चिह्नित करने के लिए और एक नोड को चिह्नित करने के लिए, जिसके सभी पड़ोसियों की खोज की गई है।

अब मेरा समाधान http://www.ideone.com/QCUmKY (महत्वपूर्ण कार्य विज़िट फ़ंक्शन है) और 10 मामलों के लिए सही चलने के बाद डब्ल्यूए देने के लिए यह वास्तव में मुश्किल है कि मैं यह कहां गलत कर रहा हूं क्योंकि यह सभी परीक्षण मामलों के लिए चलता है जो मैंने हाथ से किया है।

Answer 1

मुझे लगता है कि यहां समस्या यह है कि डीएफएस टोपोलॉजिकल सॉर्टिंग एल्गोरिदम केवल वैध स्थलीय प्रकार का उत्पादन करने की गारंटी है, न कि लेक्सिकोोग्राफिक रूप से पहले स्थलीय प्रकार (जो आपको चाहिए)।

एक तरीका जिस तरह से आप संभावित रूप से इसे ठीक कर सकते हैं यह बदलने के लिए कि आप किस एल्गोरिदम का उपयोग कर रहे हैं जो आप एक टोपोलॉजिकल सॉर्ट करने के लिए कर रहे हैं। डीएफएस का उपयोग करने के बजाय, अन्य मानक एल्गोरिदम का उपयोग करने पर विचार करें, जो इंडेक्स 0 के साथ सभी नोड्स का एक सेट बनाए रखकर काम करता है, फिर बार-बार एक को हटाकर और 0 के साथ नोड्स के सेट को अपडेट करना। यदि आप नोड को चुनने के लिए प्राथमिकता कतार का उपयोग करते हैं indgree 0 और प्रत्येक पुनरावृत्ति पर सबसे कम संख्यात्मक मूल्य के साथ, आप एक स्थलीय प्रकार वापस प्राप्त करेंगे जो समस्या से दी गई बाधाओं को पूरा करता है।

आशा है कि इससे मदद मिलती है!

Answer 2

यहाँ एक इनपुट है कि अपने कार्यक्रम टूट जाता है:

4 4 
2 4 
4 1 
3 1 

जवाब 2 3 4 1 होना चाहिए, लेकिन अपने कोड प्रिंट 3 2 4 1.

कारण है कि आप कोने की यात्रा है इंडेक्स ऑर्डर में; हालांकि, एक उच्च आदेश सूचकांक कम सूचकांक नोड का कारण बन सकता है।

इस समस्या के लिए एक सरल ओ (एम + nlogn) समाधान होना चाहिए, लेकिन मैं नहीं देख सकता कि आपके कोड को आसानी से कैसे ठीक किया जाए। जब आप लिखते हैं, तो आप इस कोड को सबसे अच्छा जानते हैं, इसलिए इसे ठीक करने में शुभकामनाएं।

Answer 3

डीएफएस एल्गोरिदम इस विशेष प्रश्न में बाहर निकलता है। कुछ चतुर चाल के साथ आप ओ (एम) के समाधान की जटिलता प्राप्त कर सकते हैं। क्रमशः सभी किनारों को क्रमबद्ध करने के लिए आप जिस प्रकार का उपयोग कर रहे हैं उसे खत्म करने की आवश्यकता है। मैंने रिवर्स किनारों की एक सूची बनाए रखी, यानी दो किनारों के लिए-- v और w-> v, मैंने शुरुआत में उन्हें सूची ली [v] -> u-> w में जोड़ा। और उसके बाद 1 से n तक ट्रैवर्सिंग, मैंने सही निर्देशित किनारों को बनाया, लेकिन इस बार वे स्वचालित रूप से क्रम में आते हैं।

वैसे भी इस बार (मेरे लिए टेस्ट केस 12 पर)। इसके लिए आपको एक बहुत ही अनुकूलित एल्गोरिदम चाहिए। एल्गोरिदम templatetypedef का उल्लेख ठीक काम करता है, शायद डीएफएस में रिकर्सन ओवरहेड डीएफएस एल्गोरिदम में थोड़ा अधिक है।

विचार बहुत आसान है, तो आप के बारे में इस यहाँ http://en.wikipedia.org/wiki/Topological_sorting

पढ़ सकते है मूल रूप से, आप शून्य indegree साथ कार्यों को पूरा कर सकते हैं और एक बार काम पूरा हो गया है, तो आप बाहर जाने वाले सभी किनारों को हटाने और सभी indegrees को अद्यतन करने और शून्य अनिश्चितता के साथ एक और कार्य खोजें। चीजों को क्रम में प्राप्त करने के लिए, आप प्राथमिकता कतार का उपयोग कर सकते हैं।

#include <iostream> 
#include <vector> 
#include <queue> 

using namespace std; 
int indeg[10005]; 
int topo[10005]; 
vector <int> g[10005]; 
int main(){ 
     int n,m; 
     int cur= 0; 
     cin >> n >> m; 
     for (int i = 0; i < m; i++){ 
       int x,y; 
       scanf("%d %d" ,&x, &y); 
       indeg[y]++; 
       g[x].push_back(y); 
     } 
     priority_queue <int> q; 
     for(int i = 1; i <= n; i++) 
       if (!indeg[i]) q.push(-1*i); 
     while(!q.empty()){ 
       int nd = -1 * q.top(); 
       q.pop(); 
       for(int i = 0; i < g[nd].size(); i++){ 
         indeg[g[nd][i]]--; 
         if (!indeg[g[nd][i]]) 
           q.push(-1*g[nd][i]); 
       } 
       topo[cur++] = nd; 
     } 
     if (cur!= n){ 
       cout << "Sandro fails." << endl; 
       return 0; 
     } 

     for(int i = 0; i < n-1; i++) 
       printf("%d ", topo[i]); 
     printf("%d\n", topo[n-1]); 


     return 0; 
}