D - Tying Rope

There are $N$ ropes numbered $1$ through $N$. One end of each rope is painted red, and the other is painted blue.

You are going to perform $M$ operations of tying ropes. In the $i$-th operation, you tie the end of rope $A_i$ painted $B_ i$ with the end of rope $C_i$ painted $D_i$, where R means red and B means blue. For each rope, an end with the same color is not tied multiple times.

Find the number of groups of connected ropes that form cycles, and the number of those that do not, after all the operations.

Here, a group of connected ropes {${v_0,v_1,…,v_{x-1}}$} is said to form a cycle if one can rearrange the elements of $v$ so that, for each $0≤i<x$, rope $v_i$ is tied to rope $v_{(i+1) mod x}$

样例

blablabla

$DFS$

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

bitset<N> vis;        // 用位图存储每个绳子是否被访问过
vector<int> vec[N];   // 用邻接表存储每个绳子连接的其他绳子的编号
int n, m, x, y, a, b; // n是绳子数量，m是操作数量，x和y是输入的绳子编号，a和b是输出的环和路径的数量
char ch;              // 输入的颜色字符，没有用到；一个绳子一端只用一次，同一种组合(Ai,Bi)不会重复出现

bool dfs(int dep, int fa)
{ // 深度优先搜索函数，dep是当前绳子编号，fa是上一个访问的绳子编号
    if (vis[dep])
    { // 如果当前绳子已经被访问过，说明找到了一个环，返回true
        return true;
    }
    vis[dep] = true; // 标记当前绳子已经被访问过
    for (auto i : vec[dep])
    { // 遍历与当前绳子相连的其他绳子
        if (i != fa && dfs(i, dep))
        { // 如果不是上一个访问的绳子，并且从它开始搜索也找到了环，返回true
            return true;
        }
    }
    return false; // 如果没有找到环，返回false
}

int main()
{
    cin >> n >> m; // 读入绳子数量和操作数量
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> ch >> y >> ch; // 读入每次操作的信息，颜色字符没有用到
        vec[x].push_back(y);       // 将y添加到x连接的列表中
        vec[y].push_back(x);       // 将x添加到y连接的列表中
    }

    // for(int i = 1; i <= n; i ++ )
    // {
    //     for(auto j: vec[i])
    //     {
    //         cout << j << " "; 
    //     }
    //     cout << endl;
    // }

    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {                        // 如果当前绳子没有被访问过
            int res = dfs(i, 0); // 从它开始深度优先搜索，并记录结果
            a += (res);          // 如果结果为true，说明找到了一个环，a加一
            b += (!res);         // 如果结果为false，说明找到了一个路径，b加一
        }
    }
    cout << a << " " << b; // 输出答案
    return 0;
}

$BFS$

Consider the $N$ ropes as $N$ vertices of a graph, and connecting ropes $a$ and $b$ as an edge connecting vertices $a$ and $b$; then the problem is rephrased as follows.

• You are given a graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertices $A_i$ and $C_i$. Every vertex has a degree at most two. Each component is either a cycle or a path; how many cycles and paths are there?

A connected component is a cycle if and only if the degree of every vertex is two, so one can store the degree of each vertex and check if each connected component forms a cycle with BFS (Breadth-First Search) for example; this way, the problem has been solved in a total of $O(N+M)$ time.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>());
    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
        int a, c;
        char b, d;
        cin >> a >> b >> c >> d;
        a--; c--;
        graph[a].push_back(c);
        graph[c].push_back(a);
        deg[a]++; deg[c]++;
    }
    int x = 0, y = 0;
    vector<bool> used(n);
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            queue<int> que;
            used[i] = true;
            que.push(i);
            bool f = true;
            while (!que.empty()) {
                int q = que.front(); que.pop();
                if (deg[q] != 2) f = false;
                for (int v : graph[q]) {
                    if (!used[v]) {
                        que.push(v);
                        used[v] = true;
                    }
                }
            }
            if (f) x++;
            else y++;
        }
    }
    cout << x << ' ' << y << '\n';
}