2 条题解
-
0
20241219尝试教的新代码：
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; vector<pair<int,int>>G[N]; int id,cnt,dfn[N],low[N],dcc[N],cut[N],root; void tarjan(int x,int in_id) { dfn[x]=low[x]=++id; int child=0; for(auto i:G[x])if(i.second!=in_id) { int y=i.first,id=i.second; if(dfn[y]==0) { tarjan(y,id); low[x]=min(low[x],low[y]); if(dfn[x]<=low[y]) { child++; if(x!=root || child>1)cut[x]++; } } else low[x]=min(low[x],dfn[y]); } } int d[N]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y);x++,y++; d[x]++;d[y]++; G[x].push_back({y,i});G[y].push_back({x,i}); } id=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); int cnt=0; for(int i=1;i<=n;i++)if(dfn[i]==0)cnt++,root=i,tarjan(i,0); int ans=0; for(int i=1;i<=n;i++) if(d[i]==0)ans=max(ans,cnt-1); else ans=max(ans,cnt+cut[i]); printf("%d\n",ans); } return 0; }代码：
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; vector<int>G[N]; int id,cnt,dfn[N],low[N],dcc[N],cut[N],root; void tarjan(int x) { dfn[x]=low[x]=++id; int child=0; for(int y:G[x]) { if( dfn[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); if(dfn[x]<=low[y]) { child++; if(x!=root || child>1)cut[x]++; } } else low[x]=min(low[x],dfn[y]); } } int d[N]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y);x++,y++; d[x]++;d[y]++; G[x].push_back(y);G[y].push_back(x); } id=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); int cnt=0; for(int i=1;i<=n;i++)if(dfn[i]==0)cnt++,root=i,tarjan(i); int ans=0; for(int i=1;i<=n;i++) if(d[i]==0)ans=max(ans,cnt-1); else ans=max(ans,cnt+cut[i]); printf("%d\n",ans); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:58:54
20241219尝试教的新代码：
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; vector<pair<int,int>>G[N]; int id,cnt,dfn[N],low[N],dcc[N],cut[N],root; void tarjan(int x,int in_id) { dfn[x]=low[x]=++id; int child=0; for(auto i:G[x])if(i.second!=in_id) { int y=i.first,id=i.second; if(dfn[y]==0) { tarjan(y,id); low[x]=min(low[x],low[y]); if(dfn[x]<=low[y]) { child++; if(x!=root || child>1)cut[x]++; } } else low[x]=min(low[x],dfn[y]); } } int d[N]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y);x++,y++; d[x]++;d[y]++; G[x].push_back({y,i});G[y].push_back({x,i}); } id=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); int cnt=0; for(int i=1;i<=n;i++)if(dfn[i]==0)cnt++,root=i,tarjan(i,0); int ans=0; for(int i=1;i<=n;i++) if(d[i]==0)ans=max(ans,cnt-1); else ans=max(ans,cnt+cut[i]); printf("%d\n",ans); } return 0; }
代码：#include<bits/stdc++.h> using namespace std; const int N=1e4+10; vector<int>G[N]; int id,cnt,dfn[N],low[N],dcc[N],cut[N],root;
</p>void tarjan(int x) { dfn[x]=low[x]=++id; int child=0; for(int y:G[x]) {
if( dfn[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); if(dfn[x]<=low[y]) { child++; if(x!=root || child>1)cut[x]++; } } else low[x]=min(low[x],dfn[y]); }} int d[N]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n0&&m0) break; memset(G,0,sizeof(G)); memset(d,0,sizeof(d)); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y);x++,y++; d[x]++;d[y]++; G[x].push_back(y);G[y].push_back(x); } id=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); int cnt=0; for(int i=1;i<=n;i++)if(dfn[i]==0)cnt++,root=i,tarjan(i);
int ans=0; for(int i=1;i<=n;i++) if(d[i]==0)ans=max(ans,cnt-1); else ans=max(ans,cnt+cut[i]); printf("%d\n",ans); } return 0;}
- 1
