82962024-01-14 11:45:27zsomborMaximális kaktusz (45 pont)cpp17Accepted 45/4552ms13784 KiB
#include <iostream>
#include <vector>
using namespace std;

int n, m, a, b, ans = 0;
vector <vector <int>> g(1e5);
vector <int> p(1e5, 0);
vector <bool> fa(1e5, true);
vector <bool> szabad;

void dfs1(int x) {
    for (int i : g[x]) {
        if (i == p[x]) continue;
        if (p[i]) {
            a = x;
            if (fa[x]) while (a != p[i]) { fa[a] = false; a = p[a]; }
            continue;
        }
        p[i] = x;
        dfs1(i);
    }
}

void dfs2(int x) {
    fa[x] = false;
    int c = 0;
    for (int i : g[x]) {
        if (!fa[i]) continue;
        p[i] = x;
        dfs2(i);
        if (szabad[i]) c++;
    }
    if (!szabad[x]) return;
    if (c >= 2) {
        ans++;
        szabad[x] = false;
    }
    if (c == 1 && p[x] > 0 && szabad[p[x]]) {
        ans++;
        szabad[x] = false;
        szabad[p[x]] = false;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    p[1] = -1;
    dfs1(1);
    fill(p.begin(), p.end(), 0);
    szabad = fa;
    for (int i = 1; i <= n; i++) {
        if (!fa[i]) continue;
        p[i] = -1;
        dfs2(i);
    }
    cout << ans;
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/04ms7168 KiB
2Accepted0/04ms7468 KiB
3Accepted1/14ms7680 KiB
4Accepted1/14ms7696 KiB
5Accepted1/14ms7948 KiB
6Accepted2/24ms8292 KiB
7Accepted2/24ms8488 KiB
8Accepted2/24ms8768 KiB
9Accepted1/14ms8804 KiB
10Accepted1/14ms8876 KiB
11Accepted1/14ms9036 KiB
12Accepted1/14ms8892 KiB
13Accepted1/14ms9020 KiB
14Accepted1/14ms8936 KiB
15Accepted1/16ms8888 KiB
16Accepted1/16ms9020 KiB
17Accepted1/14ms8916 KiB
18Accepted1/150ms12096 KiB
19Accepted1/145ms12420 KiB
20Accepted1/152ms12096 KiB
21Accepted1/150ms12288 KiB
22Accepted2/239ms12392 KiB
23Accepted2/239ms12480 KiB
24Accepted2/239ms12264 KiB
25Accepted2/239ms12496 KiB
26Accepted1/14ms8864 KiB
27Accepted1/14ms8864 KiB
28Accepted1/14ms9116 KiB
29Accepted1/148ms12764 KiB
30Accepted1/150ms12852 KiB
31Accepted1/145ms13124 KiB
32Accepted1/146ms13060 KiB
33Accepted2/248ms13096 KiB
34Accepted2/248ms13236 KiB
35Accepted2/245ms13504 KiB
36Accepted2/243ms13784 KiB