社区讨论
求助,搞不定了
P3916图的遍历参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo1unvgz
- 此快照首次捕获于
- 2023/10/23 03:16 2 年前
- 此快照最后确认于
- 2023/11/03 03:47 2 年前
u->v时,我的想法是利用dfs的回溯返回v可以到达的最大值,再将其与u可以到达的最大值比较更新maxTo[u]。
WA了很多发。不知为啥。
当测试数据为环,或者一个起点或者一个树的时候感觉都没有试出来错误。
下载了第一个测试点,有37个点,实在没法找错。
求助大佬!!!
CPP#include <iostream>
using namespace std;
//链式前向星存图
const int MAXV=100010;
const int MAXE=100010;
struct Edge{
int ne;
int v;
int w;
}e[MAXE];
int head[MAXV];
int MAXTO[MAXV];
bool Graph_vis[MAXV];
int Graph_cnt=1;
int MAXVGo(int u){
if(Graph_vis[u]) return MAXTO[u];
Graph_vis[u]=1;
int max_get=u;
MAXTO[u]=max({max_get,MAXTO[u]});
for (int i=head[u]; ~i; i=e[i].ne) {
MAXTO[u]=max({max_get,MAXVGo(e[i].v),MAXTO[u]});
}
return MAXTO[u];
}
void init(){
for(int i=0;i<MAXV;i++) head[i]=-1;
return;
}
void add(int u,int v,int w){
e[Graph_cnt].w=w;
e[Graph_cnt].v=v;
e[Graph_cnt].ne=head[u];
head[u]=Graph_cnt++;
return;
}
void solve();
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; //cin>>T;
T=1;
while (T--) solve();
return 0;
}
void solve(){
int n,m;
cin>>n>>m;
init();
for (int i=1; i<=m; i++) {
int a,b;
cin>>a>>b;
add(a,b,0);
}
for (int i=1; i<=n; i++) {
if(!Graph_vis[i]){
MAXVGo(i);
}
}
for (int i=1; i<=n; i++) {
cout<<MAXTO[i]<<" ";
}
cout<<endl;
return;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...