D - Tying Rope

D - Tying Rope (atcoder.jp)

这个题的目的是判断自环。根据题意，当这两条绳子出现两次的时候他们就连成了自环，所以我们可以根据这个判断他们是否能连成自环。首先我们要记录下每次连接的两端绳子，然后我们用并查集记录下来。用并查集合并他们。第二次再遇到这两条绳子的时候，这两条绳子之前已经合并了，所以他们一定能连成自环 ，ans1 ++。然后每次连接的时候都会有两个绳子变成不是单独一条的，所以每次ans2 --。因为每次ans2 都要减，所以可以放在最后再减。

代码如下：

#include 
#define int long long 
using namespace std;
constexpr int N = 2e5 + 10;
int f[N];
int find(int x)
{return x == f[x] ? f[x] : f[x] = find(f[x]);
}signed main()
{int n, m; cin >> n >> m;int ans1 = 0, ans2 = n;for (int i = 1; i <= n; i ++) f[i] = i;for (int i = 1; i <= m; i ++){int a, b;char c, d;cin >> a >> c >> b >> d;if (find(a) == find(b)) ans2 --, ans1 ++; // 如果这两个数已经在一个共同祖先上了，再连一次就会形成闭环，所以 ans1 ++， 每次相连的时候都会少一个单独的，所以 ans2 --；// 可以判断他们是否连接 else {f[find(a)] = find(b), ans2 --;}}cout << ans1 << " " << n - m << "\n";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！