题解：AT_abc393_c [ABC393C] Make it Simple

yyycj · 2025-02-17 20:38:13 · 题解

题目传送门

题目简述

给定一个 N 个顶点 M 条边的图，求至少需要去掉几条边才能使这个图无自环和重边。

主要思路

判断自环比较好判断，只要 u = v 就将答案加 1。判断重边可以维护一个 map，键类型为 pair<int, int>，值类型为 int，表示边的两个顶点分别是 pair 中的两个值出现了几次。

每次输入 u 和 v 时，如果不是自环，则让键为 u 和 v 以升序组成的 pair 加 1，升序是因为要让顶点相同但可能顺序不同的边算为同一条边。最后遍历每个值，如果某个值大于 1，则表示出现了重边，将答案增加值减 1。

AC Code

#include<map>
#include<cstdio>
#include<iostream>
using namespace std;

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif

#define endl '\n'
#define pc putchar
#define gc getchar
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
void print(int x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
inline int read_int() { int f = 1, x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }return x * f; }
// ----------------------------

// ----------------------------
map<pii, int> mp;
// ----------------------------

int main() {
    int u, v, ans = 0, n = read_int(), m = read_int();
    rep(i, 1, m) {
        u = read_int(), v = read_int();
        if (u == v) ans++;
        else {
            if (u > v) swap(u, v);
            mp[make_pair(u, v)]++;
        }
    }
    // ----------------------------
    for (auto i : mp) ans += i.second - 1;
    // ----------------------------
    print(ans);
    return 0;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/