首页 > 代码库 > UVAlive 5796 Hedge Mazes

UVAlive 5796 Hedge Mazes

2024-07-21 06:58:28   210人阅读

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3807

题意：给一个图，有R个点C条边，会进行Q次询问。每次询问两个点u，v之间有没有为一条路径相联。

题解：如果两个点只有唯一一条路径，那么它们之间的路径里的边就要是桥，并且需要在同一联通块上。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cmath>  4 #include <algorithm>  5 #include <ctime>  6 #include <cstdlib>  7 #include <cstring>  8 #include <map>  9 #include <stack> 10 #include <queue> 11 #include <set> 12 #include <vector> 13 #include <functional> 14  15 using namespace std; 16  17 const int maxv=10010; 18 const int maxe=100010; 19  20 vector<int> G[maxv]; 21 int par[maxv]; 22 int rankh[maxv]; 23 int pre[maxv]; 24 int dfs_clock; 25 int R,C,Q; 26 int V; 27  28 void init(int n) 29 { 30     for(int i=0;i<=n;i++) 31     { 32         par[i]=i; 33         rankh[i]=0; 34     } 35 } 36  37 int findpar(int x) 38 { 39     if(par[x]==x){ 40         return x; 41     }else{ 42         return par[x]=findpar(par[x]); 43     } 44 } 45  46 void unite(int x,int y) 47 { 48     x=findpar(x); 49     y=findpar(y); 50     if(x==y) return; 51     if(rankh[x]<rankh[y]){ 52         par[x]=y; 53         rankh[y]+=rankh[x]; 54     }else{ 55         par[y]=x; 56         rankh[x]+=rankh[y]; 57     } 58 } 59  60 int dfs(int u,int fa) 61 { 62     int lowu=pre[u]=++dfs_clock; 63     for(int i=0;i<G[u].size();i++) 64     { 65         int v=G[u][i]; 66         if(!pre[v]){ 67             int lowv=dfs(v,u); 68             lowu=min(lowu,lowv); 69             if(lowv==pre[v]) unite(u,v); 70         } 71         else if(v!=fa) lowu=min(lowu,pre[v]); 72     } 73     return lowu; 74 } 75  76 void iscut() 77 { 78     memset(pre,0,sizeof(pre)); 79     for(int i=0;i<V;i++) 80     { 81         if(!pre[i]){ 82             dfs_clock=0; 83             dfs(i,-1); 84         } 85     } 86 } 87  88 int main() 89 { 90 #ifdef PIT 91     freopen("H.in", "r", stdin); 92 #endif // PIT 93     while(scanf("%d%d%d",&R,&C,&Q)!=EOF) 94     { 95         if(R+C+Q==0) break; 96         for(int i=0;i<R;i++) 97         { 98             G[i].clear(); 99         }100         V=R;101         init(V);102         for(int i=0;i<C;i++)103         {104             int u,v;105             scanf("%d %d",&u,&v);106             u-=1;107             v-=1;108             G[u].push_back(v);109             G[v].push_back(u);110         }111         iscut();112         for(int i=0;i<Q;i++)113         {114             int u,v;115 116             scanf("%d%d",&u,&v);117             u-=1;118             v-=1;119             if(findpar(u)==findpar(v))120                 puts("Y");121             else puts("N");122         }123         puts("-");124     }125     return 0;126 }

 

UVAlive 5796 Hedge Mazes


联系
我们