首页 > 代码库 > fzu2181(点的双连通分量+求奇环)
fzu2181(点的双连通分量+求奇环)
求出每个点双连通分量,如果在一个点双连通分量中有奇环,则这个分量每个点都在一个奇环中。 关键是要知道怎么求点双连通分量以及点双连通的性质。
fzu2181 http://acm.fzu.edu.cn/problem.php?pid=2181
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 1100int n,m,k;int g[N][N];int vis[N];int height[N];int stk[N];int deep,top;int mark[N];int save[N]; //用来记录特殊状态int ans;int dfs(int s,int num){ vis[s]=deep++; stk[top++]=s; height[s]=num; int mi=vis[s]; for(int i=1;i<=n;i++) { if(g[s][i]==0) continue; if(vis[i]==-1) //这个点未被访问 { dfs(i,num+1); if( vis[i]>=vis[s] )//表示这个圈与世无争,必须单独处理掉 { //开始处理! int cnt=0; int tcnt=0; int flag=0; while(stk[top-1]!=s) { cnt++; if(mark[stk[top-1]]==1) flag=1;//表示这一堆有奇环 if(save[stk[top-1]]==1) tcnt++; top--; } if(flag==1)//这一堆不存在奇环 { save[s]=1; ans += cnt+1-tcnt; } } else { mi = min(mi,vis[i]); } } else { mi=min(mi,vis[i]);//找当前能到达最上方的点 if( (height[s]-height[i])%2==0 )//表示当前点在一个奇环中 mark[s]=1; } } vis[s]=mi; return vis[s];}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); memset(g,0,sizeof(g)); for(int i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); g[x][y]=g[y][x]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j) g[i][j]=0; else if(g[i][j]==1) g[i][j]=0; else g[i][j]=1; } //构建逆图 memset(vis,-1,sizeof(vis)); memset(save,0,sizeof(save)); memset(mark,0,sizeof(mark)); deep=0; top=0; ans=0;//表示有多少不能参与游戏 for(int i=1;i<=n;i++) { if(vis[i]==-1) { dfs(i,0); } } if(ans<k) printf("What a Pity.\n"); else printf("Let‘s Fire!\n"); } return 0;}
fzu2181(点的双连通分量+求奇环)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。