社区讨论
求助,为什么洛谷上能过,ACwing上连样例都过不了
P2860[USACO06JAN] Redundant Paths G参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mhjsffbh
- 此快照首次捕获于
- 2025/11/04 07:45 4 个月前
- 此快照最后确认于
- 2025/11/04 07:45 4 个月前
rt, 洛谷评测记录,同一个代码,这两个题的样例也是一样的,为什么Acwing上这个代码样例输出的是1,DEV和洛谷的都是2
CPP#include<iostream>
#include<cmath>
using namespace std;
const int N=1e4+500;
int n,m;
struct str{
int u,v,nxt;
}a[N],b[N];
int tot1=1,tot2=1;
int head1[N],head2[N];
int dfn[N],low[N];
int id;
int br[N];
int cnt;
int f[N];
int ans;
int c[N];
int num;
void add1(int u,int v){
a[++tot1].v=v;
a[tot1].u=u;
a[tot1].nxt=head1[u];
head1[u]=tot1;
}
void add2(int u,int v){
b[++tot2].u=u;
b[tot2].v=v;
b[tot2].nxt=head2[u];
head2[u]=tot2;
}
void tarjan(int x,int fa){
dfn[x]=low[x]=++id;
for(int i=head1[x];i;i=a[i].nxt){
int y=a[i].v;
if(y==fa) continue;
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
br[i]=br[i^1]=1;
}
}else{
low[x]=min(dfn[y],low[x]);
}
}
return ;
}
void dfs(int x){
c[x]=num;
for(int i=head1[x];i;i=a[i].nxt){
int v=a[i].v;
if(c[v]||br[i]) continue;
dfs(v);
}
return ;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
scanf("%ld%ld",&u,&v);
add1(u,v);
add1(v,u);
}
//cout<<tot1<<endl;
tarjan(1,0);
for(int i=1;i<=n;i++){
if(!c[i]){
num++;
dfs(i);
}
}
/*for(int i=1;i<=2*m+2;i++){
cout<<br[i]<<endl;
}*/
for(int i=1;i<=tot1;i++){
int u=a[i].u;
int v=a[i].v;
if(c[u]!=c[v]){
add2(c[u],c[v]);
add2(c[v],c[u]);
f[c[u]]++;
//cout<<u<<" "<<v<<endl;
}
}
//cout<<tot1<<endl;
for(int i=1;i<=num;i++){
if(f[i]==1) ans++;
}
cout<<(ans+1)/2;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...