首页 > 代码库 > zoj3583Simple Path【并查集（思想很好）】

zoj3583Simple Path【并查集（思想很好）】

2024-07-23 11:22:28   216人阅读

大意：

告诉你一个无向图

然后定义一个simple path是一条路径上面不包含重复的点

然后告诉你两个点s， t

问有多上个点是不在s到t的simple路径上

 

分析：

对于从s到t的simple path上  无论删除其他的任何一个 点   那么这个点一定是要么和s相连，要么和t相连

从这个角度出发的话

如果删除任何一点

如果有个点突然不和s，或t相连了

那么改点也就一定不是该simple path上的点

最后统计一下个数即可

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 105; 7 int a[maxn * maxn], b[maxn * maxn]; 8 int vis[maxn]; 9 int fa[maxn];10 11 int Find(int i) {12     if(fa[i] == i) return i;13     return fa[i] = Find(fa[i]);14 }15 16 void Union(int u, int v) {17     int fu = Find(u); int fv = Find(v);18     if(fu != fv) {19         fa[fu] = fv;20     }21 }22 23 int main() {24     int n, m, s, t;25     while(EOF != scanf("%d %d %d %d",&n, &m, &s, &t) ) {26         for(int i = 1; i <= m; i++) {27             scanf("%d %d",&a[i], &b[i]);28         }29         memset(vis,0, sizeof(vis));30         for(int i = 0; i < n; i++) {31             for(int j = 0; j <= n; j++) fa[j] = j;32             for(int j = 1; j <= m; j++) {33                 if(a[j] != i && b[j] != i) {34                     Union(a[j], b[j]);35                 }36             }37             for(int j = 0; j < n; j++) {38                 if(j != i && Find(j) != Find(s) && Find(j) != Find(t)) {39                     vis[j] = 1;40                 }41             }42         }43         int ans = 0;44         for(int i = 0; i < n; i++) {45             if(vis[i]) {46                    ans++;47             }48         }49         printf("%d\n",ans);50     }    51     return 0;52 }
View Code

 

zoj3583Simple Path【并查集（思想很好）】


联系
我们