【C++】洛谷P3916图的遍历-创新互联

给出 N N N 个点， M M M 条边的有向图，对于每个点 v v v，求 A ( v ) A(v) A(v) 表示从点 v v v 出发，能到达的编号大的点。

第 1 1 1 行 2 2 2 个整数 N , M N,M N,M，表示点数和边数。

接下来 M M M 行，每行 2 2 2 个整数 U i , V i U_i,V_i Ui​,Vi​，表示边 ( U i , V i ) (U_i,V_i) (Ui​,Vi​)。点用 1 , 2 , … , N 1,2,\dots,N 1,2,…,N 编号。

一行 N N N 个整数 A ( 1 ) , A ( 2 ) , … , A ( N ) A(1),A(2),\dots,A(N) A(1),A(2),…,A(N)。

4 3
1 2
2 4
4 3

4 4 3 4

• 对于 60 % 60\% 60% 的数据， 1 ≤ N , M ≤ 1 0 3 1 \leq N,M \leq 10^3 1≤N,M≤103。
• 对于 100 % 100\% 100% 的数据， 1 ≤ N , M ≤ 1 0 5 1 \leq N,M \leq 10^5 1≤N,M≤105。

思路： 直接强行从每一个点遍历一次整个图会超时，所以需要换一种方法。
由于这是个有向图，那么在按照图的方向遍历时，例如从a->b时，若经过了b那么就一定可以经过a。所以我们可以将有向图的方向倒置（a->b的图就变成了b->a的图），然后由题意，我们需要寻找编号大的点，因此可以从大的点开始遍历，此时遍历的路径上的所有点能到达的大点就是此时的起始点。
按照这个思路将图遍历一次即可。因为每个点只会被遍历一次，所以不会超时。

代码：

#includeusing namespace std;
int n, m, ans[100005];
bool vis[100005];
vectorvec[100005];
void dfs(int st, int maxx){vis[st] = true;
    maxx = max(st, maxx);
    ans[st] = max(maxx, ans[st]);
    for(int i = 0; i< vec[st].size(); i++){int to = vec[st][i];
        if(!vis[to]) dfs(to, maxx);
    }
    return;
}
int main(){cin >>n >>m;
    for(int i = 1; i<= m; i++){int x, y;
        cin >>x >>y;
        vec[y].push_back(x);
    }
    for(int i = 1; i<= n; i++) ans[i] = i;
    for(int i = n; i >= 1; i--) if(!vec[i].empty()) dfs(i,-1);
    for(int i = 1; i<= n; i++) printf("%d ", ans[i]);
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧