$O(M)$-এ অয়লারিয়ান পাথ বের করা#

একটি অয়লারিয়ান পাথ হল একটি গ্রাফের এমন একটি পাথ যা এর সমস্ত এজ দিয়ে ঠিক একবার যায়। একটি অয়লারিয়ান সাইকেল হল একটি অয়লারিয়ান পাথ যা একটি সাইকেল।

সমস্যাটি হল একটি লুপসহ আনডিরেক্টেড মাল্টিগ্রাফে অয়লারিয়ান পাথ খুঁজে বের করা।

অ্যালগরিদম#

প্রথমে আমরা পরীক্ষা করতে পারি অয়লারিয়ান পাথ আছে কি না। আমরা নিম্নলিখিত উপপাদ্য ব্যবহার করতে পারি। একটি অয়লারিয়ান সাইকেল বিদ্যমান যদি এবং কেবল যদি সমস্ত ভার্টেক্সের ডিগ্রি জোড় হয়। এবং একটি অয়লারিয়ান পাথ বিদ্যমান যদি এবং কেবল যদি বিজোড় ডিগ্রিযুক্ত ভার্টেক্সের সংখ্যা দুই হয় (অথবা শূন্য, অয়লারিয়ান সাইকেল থাকার ক্ষেত্রে)। এছাড়াও, অবশ্যই, গ্রাফটি যথেষ্ট সংযুক্ত হতে হবে (অর্থাৎ, সমস্ত বিচ্ছিন্ন ভার্টেক্স সরিয়ে দিলে একটি সংযুক্ত গ্রাফ পাওয়া উচিত)।

অয়লারিয়ান পাথ / অয়লারিয়ান সাইকেল খুঁজে পেতে আমরা নিম্নলিখিত কৌশল ব্যবহার করতে পারি: আমরা সমস্ত সিম্পল সাইকেল খুঁজি এবং তাদের একটিতে একত্রিত করি - এটিই অয়লারিয়ান সাইকেল হবে। গ্রাফটি এমন হলে যে অয়লারিয়ান পাথ একটি সাইকেল নয়, তাহলে অনুপস্থিত এজটি যোগ করি, অয়লারিয়ান সাইকেল খুঁজি, তারপর অতিরিক্ত এজটি সরিয়ে দিই।

সমস্ত সাইকেল খোঁজা এবং একত্রিত করা একটি সাধারণ রিকার্সিভ প্রসিডিউর দিয়ে করা যায়:

procedure FindEulerPath(V)
  1. iterate through all the edges outgoing from vertex V;
       remove this edge from the graph,
       and call FindEulerPath from the second end of this edge;
  2. add vertex V to the answer.

এই অ্যালগরিদমের কমপ্লেক্সিটি স্পষ্টতই এজের সংখ্যার সাপেক্ষে লিনিয়ার।

তবে আমরা একই অ্যালগরিদম নন-রিকার্সিভ ভার্সনে লিখতে পারি:

stack St;
put start vertex in St;
until St is empty
  let V be the value at the top of St;
  if degree(V) = 0, then
    add V to the answer;
    remove V from the top of St;
  otherwise
    find any edge coming out of V;
    remove it from the graph;
    put the second end of this edge in St;

এই দুটি রূপের সমতুল্যতা যাচাই করা সহজ। তবে, দ্বিতীয় রূপটি স্পষ্টতই দ্রুততর, এবং কোডটি অনেক বেশি কার্যকর হবে।

ডমিনো সমস্যা#

এখানে আমরা একটি ক্লাসিক অয়লারিয়ান সাইকেল সমস্যা দিই - ডমিনো সমস্যা।

$N$টি ডমিনো আছে, যেমনটি জানা যায়, ডমিনোর উভয় প্রান্তে একটি সংখ্যা লেখা থাকে (সাধারণত ১ থেকে ৬, কিন্তু আমাদের ক্ষেত্রে এটি গুরুত্বপূর্ণ নয়)। আপনি সমস্ত ডমিনো একটি সারিতে রাখতে চান যাতে যেকোনো দুটি পাশাপাশি ডমিনোর, তাদের সাধারণ পাশে লেখা সংখ্যা, মিলে যায়। ডমিনো ঘোরানো যায়।

সমস্যাটি পুনর্গঠন করি। ধরি নিচে লেখা সংখ্যাগুলো গ্রাফের ভার্টেক্স, এবং ডমিনোগুলো এই গ্রাফের এজ (প্রতিটি $(a,b)$ সংখ্যাযুক্ত ডমিনো হল এজ $(a,b)$ এবং $(b, a)$)। তাহলে আমাদের সমস্যা এই গ্রাফে অয়লারিয়ান পাথ খুঁজে বের করার সমস্যায় পরিণত হয়।

ইমপ্লিমেন্টেশন#

নিচের প্রোগ্রামটি একটি গ্রাফে অয়লারিয়ান লুপ বা পাথ খোঁজে এবং আউটপুট দেয়, অথবা এটি বিদ্যমান না থাকলে $-1$ আউটপুট দেয়।

প্রথমে, প্রোগ্রামটি ভার্টেক্সের ডিগ্রি পরীক্ষা করে: বিজোড় ডিগ্রিযুক্ত কোনো ভার্টেক্স না থাকলে গ্রাফে অয়লার সাইকেল আছে, বিজোড় ডিগ্রিযুক্ত $2$টি ভার্টেক্স থাকলে গ্রাফে শুধু অয়লার পাথ আছে (কিন্তু অয়লার সাইকেল নেই), $2$-এর বেশি এমন ভার্টেক্স থাকলে গ্রাফে অয়লার সাইকেল বা অয়লার পাথ কোনোটিই নেই। অয়লার পাথ (সাইকেল নয়) খুঁজতে, আমরা এটি করি: $V1$ এবং $V2$ বিজোড় ডিগ্রির দুটি ভার্টেক্স হলে, শুধু একটি এজ $(V1, V2)$ যোগ করি, ফলাফল গ্রাফে অয়লার সাইকেল খুঁজি (এটি স্পষ্টতই বিদ্যমান হবে), তারপর উত্তর থেকে “কাল্পনিক” এজ $(V1, V2)$ সরিয়ে দিই। আমরা ঠিক উপরে বর্ণিত (নন-রিকার্সিভ ভার্সন) অনুযায়ী অয়লার সাইকেল খুঁজব, এবং একই সাথে এই অ্যালগরিদমের শেষে পরীক্ষা করব গ্রাফটি সংযুক্ত ছিল কি না (গ্রাফ সংযুক্ত না হলে, অ্যালগরিদমের শেষে কিছু এজ গ্রাফে থেকে যাবে, এবং সেক্ষেত্রে আমাদের $-1$ প্রিন্ট করতে হবে)। পরিশেষে, প্রোগ্রামটি গ্রাফে বিচ্ছিন্ন ভার্টেক্স থাকতে পারে তা বিবেচনা করে।

লক্ষ্য করুন যে এই সমস্যায় আমরা একটি অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করি। এছাড়াও এই ইমপ্লিমেন্টেশনটি ব্রুট ফোর্সে পরবর্তী এজ খোঁজে, যার জন্য ম্যাট্রিক্সের সম্পূর্ণ সারিতে বারবার ইটারেট করতে হয়। একটি ভালো উপায় হবে গ্রাফটি অ্যাডজেসেন্সি লিস্ট হিসেবে সংরক্ষণ করা, এবং $O(1)$-এ এজ সরানো এবং আলাদা লিস্টে বিপরীত এজ চিহ্নিত করা। এভাবে আমরা একটি $O(N)$ অ্যালগরিদম পেতে পারি।

int main() {
    int n;
    vector<vector<int>> g(n, vector<int>(n));
    // reading the graph in the adjacency matrix

    vector<int> deg(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            deg[i] += g[i][j];
    }

    int first = 0;
    while (first < n && !deg[first])
        ++first;
    if (first == n) {
        cout << -1;
        return 0;
    }

    int v1 = -1, v2 = -1;
    bool bad = false;
    for (int i = 0; i < n; ++i) {
        if (deg[i] & 1) {
            if (v1 == -1)
                v1 = i;
            else if (v2 == -1)
                v2 = i;
            else
                bad = true;
        }
    }

    if (v1 != -1)
        ++g[v1][v2], ++g[v2][v1];

    stack<int> st;
    st.push(first);
    vector<int> res;
    while (!st.empty()) {
        int v = st.top();
        int i;
        for (i = 0; i < n; ++i)
            if (g[v][i])
                break;
        if (i == n) {
            res.push_back(v);
            st.pop();
        } else {
            --g[v][i];
            --g[i][v];
            st.push(i);
        }
    }

    if (v1 != -1) {
        for (size_t i = 0; i + 1 < res.size(); ++i) {
            if ((res[i] == v1 && res[i + 1] == v2) ||
                (res[i] == v2 && res[i + 1] == v1)) {
                vector<int> res2;
                for (size_t j = i + 1; j < res.size(); ++j)
                    res2.push_back(res[j]);
                for (size_t j = 1; j <= i; ++j)
                    res2.push_back(res[j]);
                res = res2;
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j])
                bad = true;
        }
    }

    if (bad) {
        cout << -1;
    } else {
        for (int x : res)
            cout << x << " ";
    }
}

অনুশীলন সমস্যা:#