大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
给出 N N N 个点, M M M 条边的有向图,对于每个点 v v v,求 A ( v ) A(v) A(v) 表示从点 v v v 出发,能到达的编号大的点。
成都创新互联是专业的子长网站建设公司,子长接单;提供网站设计制作、成都网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行子长网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!输入格式第 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)。
样例 #1 样例输入 #14 3
1 2
2 4
4 3
样例输出 #14 4 3 4
提示思路: 直接强行从每一个点遍历一次整个图会超时,所以需要换一种方法。
由于这是个有向图,那么在按照图的方向遍历时,例如从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元起,快前往官网查看详情吧