tarjan+拓扑序+差分--2018.10.16模拟赛T2

本文主要是介绍tarjan+拓扑序+差分--2018.10.16模拟赛T2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
阿天住的城市有 n 个政府部门，这些部门之间用了 m 条有向路径
连接了起来。有趣的是，每过一天这些路径都会变换方向，也就是说，
偶数的日子和奇数的日子的图是不同的。
阿天在社保局工作，可惜他过于丢人忘记了社保局的位置。他只
记得由于社保局很重要，它在一个可以到达所有其他部门的地点。请
你帮他找到所有满足条件的地点。

solution:
首先肯定要缩点，因为强连通分量不管怎样都会走到
然后考场上还想出了拓扑排序，但是处理方式不太对
我想的是分层然后如果这层只有一个点就可以，但之后举出了反例

正解应该是利用拓扑序和拓扑的性质
如果一个点可以到达的点和可以被到达的点加起来超过了$n$那这个点就是答案点
考虑如何计算一个点$u$可以到达哪些点，因为拓扑序有分层的特点
在去点$to[u]$中找到$id[v]$最小的，那么从$id[u]+1$到$id[v]-1$这一段都是不能被到达的，被到达和这个方法一样

就可以在拓扑序上差分然后前缀和，如果$sum[i]=0$就是答案点

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define N 1000005
using namespace std;
int n,m,cnt,head[N],eh[N],ec,sum[N],num,id[N],pos[N],pre[N];
int dfn[N],low[N],stk[N],tot,top,tim,bel[N],d[N];
bool vis[N],can[N];
vector<int> scc[N],ans;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f; 
}struct EDGE{int to,nxt; 
}edge[N],e[N];
inline void add(int x,int y){edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt;
}
inline void add2(int x,int y){e[++ec].to=y; e[ec].nxt=eh[x]; eh[x]=ec; ++d[y];
}void tarjan(int u){dfn[u]=low[u]=++tim; vis[u]=1; stk[++top]=u;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]) low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){tot++; int tmp;do{tmp=stk[top--]; vis[tmp]=0;bel[tmp]=tot; scc[tot].push_back(tmp);}while(u!=tmp);} return;
}inline void rebuild(){for(int u=1;u<=n;u++)for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(bel[v]!=bel[u]) add2(bel[u],bel[v]);}
}inline void solve(){top=0;for(int i=1;i<=tot;i++){can[i]=true;if(!d[i]) stk[++top]=i,id[i]=++num,pos[num]=i;}while(top){int u=stk[top--];for(int i=eh[u];i;i=e[i].nxt){int v=e[i].to;--d[v];if(!d[v]) stk[++top]=v,id[v]=++num,pos[num]=v;}}for(int u=1;u<=tot;u++)for(int i=eh[u];i;i=e[i].nxt){int v=e[i].to;pre[v]=max(pre[v],id[u]);//找到连到v的id最大的点 }for(int i=1;i<=num;i++){int u=pos[i];sum[pre[u]+1]++,sum[i]--;}for(int i=1;i<=num;i++){pre[i]=tot+1; sum[i]+=sum[i-1];if(sum[i]) can[pos[i]]=false;}memset(sum,0,sizeof sum);for(int u=1;u<=tot;u++)for(int i=eh[u];i;i=e[i].nxt){int v=e[i].to;pre[u]=min(pre[u],id[v]);//找到u连接的id最小的点 }for(int i=1;i<=num;i++){int u=pos[i];sum[pre[u]-1]++,sum[i]--;}for(int i=num;i;i--){sum[i]+=sum[i+1];if(sum[i]) can[pos[i]]=false;}
}int main(){freopen("wtmsb.in","r",stdin);freopen("wtmsb.out","w",stdout);n=rd(); m=rd();for(int i=1;i<=m;i++){int x=rd(),y=rd();add(x,y);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);rebuild(); solve();for(int i=1;i<=tot;i++)if(can[i])for(int j=0;j<scc[i].size();j++)ans.push_back(scc[i][j]);sort(ans.begin(),ans.end());printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);return 0;
}

这篇关于tarjan+拓扑序+差分--2018.10.16模拟赛T2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---