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

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

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