الگوریتم های راس و یال برشی

پیدا کردن یال برشی

برای پیدا کردن یال برشی، ابتدا بر روی گراف الگوریتم DFS را اجرا می کنیم. در هنگام اجرا شدن الگوریتم DFS به ازای هر راس u یک مقدار dp[u] نگه می داریم که برابر است با کمترین ارتفاعی که به آن backedge از بین رئوس زیر درخت راس u داریم. مقدار dp[u] برای هر راس این گونه حساب می شود که مقدار یک راس برابر با کمترین مقدار فرزندان آن راس و ارتفاع backedge های خود آن راس می باشد. حال یک یال بین راس v و parent[v] برشی است اگر و تنها اگر dp[v] مقدارش کمتر از ارتفاع v نباشد. یعنی یالی در زیر درخت v وجود نداشته باشد که به راسی بالا تر از v وصل باشد.

زمان اجرای این الگوریتم O(n+m) است که در آن n نشان دهنده تعداد راس ها و m نشان دهنده تعداد یال ها است.

// S 100101
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

bool mark[maxn], is[maxn];
int dp[maxn], height[maxn];
pair<int, int> edge[maxn];
vector<pair<int, int> > adj[maxn];

void dfs(int v,int parent,int index){
    dp[v] = height[v];
    mark[v] = true;
    for(int i = 0; i < adj[v].size(); i++){
        int u = adj[v][i].first;
        int ind = adj[v][i].second;
        if(!mark[u]){
            height[u] = height[v] + 1;
            dfs(u, v, ind);
            dp[v] = min(dp[v], dp[u]);
        }
        else{
            if(u != parent){
                dp[v] = min(dp[v], height[u]);
            }
        }
    }
    if(v != 1 && dp[v] == height[v])
        is[index] = true;
    return;
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 0, 0);
    for(int i = 0; i < m; i++)
        if(is[i])
            cout << edge[i].first << " " << edge[i].second << endl;
    return 0;
}

پیدا کردن راس برشی

در این قسمت نیز به مانند یال برشی مقدار dp[u] را با همان تعریف برای راس u به دست می آوریم. حال یک راس برشی است اگر وقتی آن را جدا می کنیم گراف به بیش از یک مولفه تقسیم شود بنابراین در درخت DFS که ساختیم راس v برشی است اگر مقدار dp همه فرزندانش بیشتر از مقدار ارتفاع راس v بود یعنی یالی به بالای آن نداشت. توجه کنید که ریشه زمانی برشی است که درجه یک نباشد.

زمان اجرای این الگوریتم نیز O(n+m) است.

// S 100101
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

bool mark[maxn], is[maxn];
int dp[maxn], height[maxn];
vector<int> adj[maxn];

void dfs(int v,int parent){
    dp[v] = height[v];
    mark[v] = true;
    int num = 0;
    for(int i = 0; i < adj[v].size(); i++){
        int u = adj[v][i];
        if(!mark[u]){
            height[u] = height[v] + 1;
            dfs(u, v);
            if(v != 1 && dp[u] >= height[v])
                is[v] = true;
            dp[v] = min(dp[v], dp[u]);
            num++;
        }
        else if(u != parent)
            dp[v] =min(dp[v], height[u]);
    }
    if(v == 1 && num > 1)
        is[v] = true;
    return;
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    for(int u = 1; u <= n; u++)
        if(is[u])
            cout << u << " ";
    return 0;
}