社区讨论
求助,56分tarjan缩点
P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lytho7ey
- 此快照首次捕获于
- 2024/07/20 10:07 2 年前
- 此快照最后确认于
- 2024/07/20 10:54 2 年前
邻接数组存图,tarjan缩点,统计出度。
#4 WA
#2,#9,#10,#11,#12,#13,#14,#18,#19,#20
RE
CPP#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[200000];
int c[200000],cl,dfn[200000],low[200000],dfnd,sf[200000],jl[200000],jd,f[200000],sz[200000];
// 环编号 ,top,dfs序 ,返祖边, dfs深度,入栈, dfs路径,前者top,出度,环大小
void tarjan(int x){
dfn[x]=++dfnd;
low[x]=dfn[x];
sf[x]=1;
jl[++jd]=x;
for(int i=0;i<g[x].size();i++){
if(!dfn[g[x][i]]){
tarjan(g[x][i]);
low[x]=min(low[x],low[g[x][i]]);
}else if(sf[i]){
low[x]=min(low[x],dfn[g[x][i]]);
}
}
if(dfn[x]==low[x]){
cl++;
while(jl[jd]!=x){
c[jl[jd]]=cl;
sf[jl[jd]]=0;
sz[cl]++;
jd--;
}
c[jl[jd]]=cl;
sz[cl]++;
sf[jl[jd]]=0;
jd--;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfnd=0;
tarjan(i);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
if(c[i]!=c[g[i][j]]){
f[c[i]]++;
}
}
}
int sff=0,jll;
for(int i=1;i<=cl;i++){
if(!f[i]){
sff++;
jll=i;
}
}
if(sff>1){
cout<<0;
return 0;
}else{
cout<<sz[jll];
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...