AtCoder Beginner Contest 293 - D - Tying Rope

Solost

2023 年 03 月 16 日

203 次浏览

暂无评论

1440字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F16%2Fimage.png)

## 链接

[题目链接](https://atcoder.jp/contests/abc293/tasks/abc293_d)

## solution

这道题简化之后其实就是找图中的环和线，我们先进行并查集操作，把能连接成环的都连接成环，剩下的不能连接的放那，然后用BFS搜索一下连通块的个数，用连通块的个数减去已经成环的个数就是剩下没有成环的个数。怎么判断成没成环，在进行并查集的时候，如果我们发现他们俩的父节点是同一个，那么就确定他们已经连接成环了，然后ans1++。

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int p[N];
vector<int> size(N, 1), g[N];
int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
map<int, int> vis;
void dfs(int x)
{
    vis[x] = 1;
    for (auto i : g[x]) {
        if (!vis[i]) {
            dfs(i);
        }
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    int ans1 = 0, ans2 = 0;
    vector<PII> q;
    while (m--) {
        int a, c;
        char b, d;
        cin >> a >> b >> c >> d;
        g[a].push_back(c);
        g[c].push_back(a);
        int fa = find(a), fc = find(c);
        if (fa == fc) {
            ans1++;
        } else {
            p[fc] = fa;
        }
    }
    // cout << ans2 << endl;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
            ans2++;
        }
    }
    cout << ans1 << " " << ans2 - ans1 << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 16 日