记忆DFS 50
查看原帖
记忆DFS 50
1239296
YYYYing楼主2024/10/9 21:25
#include <bits/stdc++.h>  
using namespace std;  

int n, m;   
vector<int> edge[100001];   
int far[100001];   
bool vis[100001];   

int dfs(int x) {  
    vis[x] = true;
    int maxx = far[x]; 
    for (auto i : edge[x]) {  
        if (!vis[i]) {  
            maxx = max(maxx, dfs(i));   
        } else {  
            maxx = max(maxx, far[i]);  
        }  
    }   
    far[x] = maxx; 
    return maxx;   
}  

int main() {  
    cin >> n >> m;   
    
    for (int i = 1; i <= n; i++) {  
        far[i] = i;
    }  
    
    for (int i = 1; i <= m; i++) {  
        int u, v;  
        cin >> u >> v;  
        edge[u].push_back(v);  
    }    
    
    memset(vis, false, sizeof(vis)); 
    for (int i = 1; i <= n; i++) {  
        dfs(i);  
    }  

    for (int i = 1; i <= n; i++) {  
        cout << far[i] << " ";  
    }  

    return 0;  
}
2024/10/9 21:25
加载中...