图的遍历—图的DFS—反向建边；

 

输入输出样例

输入 #1

4 3
1 2
2 4
4 3

输出 #1

4 4

第一遍自己写的tle答案；

#include 
using namespace std;
const int N = 3e5 + 10;
int n, m, ne[N], h[N], idx, e[N];
bool vis[N];
inline void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int ans;
void dfs(int u)
{
    vis[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!vis[j])
        {
            ans = max(ans, e[i]);
            dfs(j);
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i++)
    {
        if (i == n)
        {
            cout << i << ' ';
            break;
        }
        memset(vis, 0, sizeof vis);
        ans = i; //从当前结点开始访问
        dfs(i);
        cout << ans << ' ';
    }
    return 0;
}

看了题解后的AC

#include 
using namespace std;
const int N = 3e5 + 10;
int n, m, ne[N], h[N], idx, e[N];
bool vis[N];
inline void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int ans;
void dfs(int u)
{
    vis[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!vis[j])
        {
            ans = max(ans, e[i]);
            dfs(j);
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i++)
    {
        if (i == n)
        {
            cout << i << ' ';
            break;
        }
        memset(vis, 0, sizeof vis);
        ans = i; //从当前结点开始访问
        dfs(i);
        cout << ans << ' ';
    }
    return 0;
}