社区讨论
对tarjan小细节的疑惑
P2746[IOI 1996 / USACO5.3] 校园网 Network of Schools参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo26dlqd
- 此快照首次捕获于
- 2023/10/23 08:44 2 年前
- 此快照最后确认于
- 2023/11/03 09:00 2 年前
对于第19行条件判定,原来写else if(instk[to])就会WA4个点,看题解后改成else if(!scc[to])就过了
求教为什么
CPP#include<bits/stdc++.h>
using namespace std;
int const X=5e4+100;
int n,m,u,v;
int Time,dfn[X],low[X],instk[X],scc[X],cnt[X],scc_cnt;
//instk:是否在栈中 scc:每个点所属的强连通分量编号 scc_cnt:强连通分量数量
stack<int> stk;
vector<int> e[X],newE[X];
int siz[X];
void tarjan(int rt){
low[rt]=dfn[rt]=++Time;
instk[rt]=1; stk.push(rt);
for(int i=0;i<e[rt].size();i++){
int to=e[rt][i];
if(!dfn[to]){
tarjan(to);
low[rt]=min(low[rt],low[to]);
}
else if(!scc[to]){ // ▲
//原来是else if(instk[to])
low[rt]=min(low[rt],dfn[to]);
}
}
if(low[rt]==dfn[rt]){
int tp;
scc_cnt++;
do{
tp=stk.top();
stk.pop();
siz[scc_cnt]++;
scc[tp]=scc_cnt;
}while(tp!=rt);
}
return ;
}
int in[X],out[X],ans1,ans2;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>u;
while(u!=0){
if(u==0) break;
e[i].push_back(u);
cin>>u;
}
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<e[i].size();j++){
int to=e[i][j];
if(scc[i]!=scc[to]){
//newE[scc[i]].push_back(scc[to]);
in[scc[to]]++;
out[scc[i]]++;
//cout<<i<<scc[i]<<' '<<to<<scc[to]<<endl;
}
}
//cout<<scc[i]<<' ';
}
ans1=ans2=0;
for(int i=1;i<=scc_cnt;i++){
//cout<<in[i]<<' '<<out[i]<<endl;
if(in[i]==0) ans1++;
if(out[i]==0) ans2++;
}
cout<<ans1<<endl<<(scc_cnt==1?0:max(ans1,ans2))<<endl;
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...