社区讨论

对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 条回复,欢迎继续交流。

正在加载回复...