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

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

.. code-block:: cpp

    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) است.

.. code-block:: cpp

    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;
    }