$O(N+M)$ এ গ্রাফে আর্টিকুলেশন পয়েন্ট খোঁজা#

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

এখানে বর্ণিত অ্যালগরিদমটি ডেপথ-ফার্স্ট সার্চ এর উপর ভিত্তি করে এবং এর কমপ্লেক্সিটি $O(N+M)$, যেখানে $N$ হলো ভার্টেক্সের সংখ্যা এবং $M$ হলো গ্রাফে এজের সংখ্যা।

অ্যালগরিদম#

গ্রাফের একটি ইচ্ছামতো ভার্টেক্স $root$ নিন এবং সেখান থেকে ডেপথ-ফার্স্ট সার্চ চালান। নিম্নলিখিত তথ্যটি লক্ষ্য করুন (যা প্রমাণ করা সহজ):

  • ধরা যাক আমরা DFS-এ আছি, ভার্টেক্স $v\ne root$ থেকে শুরু করে এজগুলো দেখছি। যদি বর্তমান এজ $(v, to)$ এমন হয় যে ভার্টেক্স $to$ বা DFS ট্রাভার্সাল ট্রি-তে এর কোনো বংশধরের $v$ এর কোনো পূর্বসূরিতে ব্যাক-এজ না থাকে, তাহলে $v$ একটি আর্টিকুলেশন পয়েন্ট। অন্যথায়, $v$ আর্টিকুলেশন পয়েন্ট নয়।

  • বাকি ক্ষেত্র $v=root$ বিবেচনা করি। এই ভার্টেক্সটি আর্টিকুলেশন পয়েন্ট হবে যদি এবং কেবল যদি DFS ট্রি-তে এই ভার্টেক্সের একাধিক চাইল্ড থাকে।

এখন আমাদের প্রতিটি ভার্টেক্সের জন্য এই তথ্যটি দক্ষতার সাথে পরীক্ষা করা শিখতে হবে। আমরা ডেপথ-ফার্স্ট সার্চ দ্বারা গণিত “নোডে প্রবেশের সময়” ব্যবহার করব।

তাই, $tin[v]$ দিয়ে নোড $v$ এর প্রবেশ সময় বোঝাই। আমরা একটি অ্যারে $low[v]$ প্রবর্তন করি যেটি আমাদের প্রতিটি ভার্টেক্স $v$ এর জন্য তথ্য পরীক্ষা করতে দেবে। $low[v]$ হলো $tin[v]$, ব্যাক-এজ $(v, p)$ দ্বারা নোড $v$ এর সাথে সংযুক্ত প্রতিটি নোড $p$ এর প্রবেশ সময় $tin[p]$ এবং DFS ট্রি-তে $v$ এর প্রত্যক্ষ বংশধর প্রতিটি ভার্টেক্স $to$ এর $low[to]$ মানের মধ্যে সর্বনিম্ন:

$$low[v] = \min \begin{cases} tin[v] \\ tin[p] &\text{ for all }p\text{ for which }(v, p)\text{ is a back edge} \\ low[to]& \text{ for all }to\text{ for which }(v, to)\text{ is a tree edge} \end{cases}$$

এখন, ভার্টেক্স $v$ বা এর কোনো বংশধর থেকে এর কোনো পূর্বসূরিতে একটি ব্যাক এজ আছে যদি এবং কেবল যদি ভার্টেক্স $v$ এর একটি চাইল্ড $to$ থাকে যার জন্য $low[to] < tin[v]$। যদি $low[to] = tin[v]$ হয়, তাহলে ব্যাক এজ সরাসরি $v$ তে আসে, অন্যথায় এটি $v$ এর কোনো পূর্বসূরিতে আসে।

অতএব, DFS ট্রি-তে ভার্টেক্স $v$ একটি আর্টিকুলেশন পয়েন্ট হবে যদি এবং কেবল যদি $low[to] \geq tin[v]$।

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

ইমপ্লিমেন্টেশনে তিনটি ক্ষেত্র আলাদা করা প্রয়োজন: যখন আমরা DFS ট্রি-তে এজ বরাবর নিচে যাই, যখন আমরা ভার্টেক্সের পূর্বসূরিতে একটি ব্যাক এজ খুঁজে পাই এবং যখন আমরা ভার্টেক্সের প্যারেন্টে ফিরে আসি। এই ক্ষেত্রগুলো হলো:

  • $visited[to] = false$ - এজটি DFS ট্রি-র অংশ;
  • $visited[to] = true$ && $to \neq parent$ - এজটি কোনো পূর্বসূরিতে ব্যাক এজ;
  • $to = parent$ - এজটি DFS ট্রি-তে প্যারেন্টে ফিরে যায়।

এটি ইমপ্লিমেন্ট করতে, আমাদের একটি ডেপথ-ফার্স্ট সার্চ ফাংশন দরকার যেটি বর্তমান নোডের প্যারেন্ট ভার্টেক্স গ্রহণ করে।

int n; // number of nodes
vector<vector<int>> adj; // adjacency list of graph

vector<bool> visited;
vector<int> tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children=0;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] >= tin[v] && p!=-1)
                IS_CUTPOINT(v);
            ++children;
        }
    }
    if(p == -1 && children > 1)
        IS_CUTPOINT(v);
}

void find_cutpoints() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs (i);
    }
}

মূল ফাংশন হলো find_cutpoints; এটি প্রয়োজনীয় ইনিশিয়ালাইজেশন সম্পাদন করে এবং গ্রাফের প্রতিটি কানেক্টেড কম্পোনেন্টে ডেপথ-ফার্স্ট সার্চ শুরু করে।

IS_CUTPOINT(a) ফাংশন হলো একটি ফাংশন যেটি ভার্টেক্স $a$ একটি আর্টিকুলেশন পয়েন্ট হওয়ার তথ্য প্রক্রিয়া করবে, উদাহরণস্বরূপ, এটি প্রিন্ট করবে (সতর্কতা: একটি ভার্টেক্সের জন্য এটি একাধিকবার কল হতে পারে)।

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