首页 > 代码库 > hdu 3313 Key Vertex
hdu 3313 Key Vertex
一个有向图,给定起点和终点,问他的割点数,割点是指去掉这个点能使得s和t不通。s和t也是割点。
先找一条从s到t的任意路径,假如没有路的话,那么割点数为n,如果找到了一条路径的话,将这条路径上的点标记出来,首先明确一点,割点肯定不会再路径外的点上,因为去掉外面的点后,还是有刚刚那条路径的。所以现在就要看路径上的每个点是不是割点。只要把路径上的点去掉,然后从s进行bfs,路径上的点不能走,这样进行bfs的记录能探访到最远的在路径上的点为ans,假如ans等于t,那么只有两个割点s和t,如果bfs结束后ans不等于t,那么ans就是一个割点。因为去掉该点之后,无法走到之后的点了。然后从ans开始继续进行bfs直到访问到t为止。
#include <cstdio>#include <cstring>#include <queue>using namespace std;#define maxn 100000+10#define maxm 300000+100#define inf 1000000000struct Edge{ int u,v,next;}e[maxm];int head[maxn],cnt;int dis[maxn],mk[maxn];int pre[maxn];int in[maxn];int n,m;int s,t;void add(int u,int v){ e[cnt].u=u; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt++;}int solve(){ int u,v,i; memset(pre,-1,sizeof(pre)); memset(in,0,sizeof(in)); for(i=0;i<n;i++) dis[i]=-1; dis[s]=0; queue <int> Q; Q.push(s); while(!Q.empty()) { u=Q.front();Q.pop(); for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(dis[v]==-1) { dis[v]=dis[u]+1; pre[v]=u; Q.push(v); } } } if(dis[t]==-1) return n; for(i=t;i!=s;i=pre[i]) in[i]=-1; in[s]=-1; int sum=1; while(1) { int ans=-1,maxdis=-1; Q.push(s); while(!Q.empty()) { u=Q.front();Q.pop(); for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(in[v]==-1&&dis[v]>maxdis) { ans=v; maxdis=dis[v]; } else if(in[v]==0) { Q.push(v); in[v]=1; } } } sum++; if(ans==t) return sum; s=ans; }}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { int i,j; int u,v; for(i=0;i<n;i++) head[i]=-1; cnt=0; for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); } scanf("%d%d",&s,&t); printf("%d\n",solve()); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。