1 条题解

  • 0
    @ 2024-7-26 11:46:52

    对每个点分别用dfs求出答案即可,时间复杂度O(n2)O(n^2)。需要注意每次处理新的点之前,需要把标记清空。

    参考代码
    
    #include <bits/stdc++.h>
    using namespace std;
    int n, m, u, v, ans;
    vector<int> g[1005];
    bool vis[1005];//每个点是否访问过
    void dfs(int u)
    {
        vis[u] = true;
        ans = max(ans, u);
        for (int i = 0; i < g[u].size(); i++)
            if (!vis[g[u][i]])
                dfs(g[u][i]);
    }
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            cin >> u >> v;
            g[u].push_back(v);
        }
        for (int i = 1; i <= n; i++) {
            ans = 0;
            memset(vis, false, sizeof(vis));
            dfs(i);
            cout << ans << " ";
        }
    	return 0;
    }
    
    • 1

    信息

    ID
    895
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    (无)
    递交数
    23
    已通过
    13
    上传者