QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#384657#4498. Planar GraphTobo#AC ✓252ms6324kbC++171.0kb2024-04-10 08:47:302024-04-10 08:47:31

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 08:47:31]
  • 评测
  • 测评结果:AC
  • 用时:252ms
  • 内存:6324kb
  • [2024-04-10 08:47:30]
  • 提交

answer

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

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vector<array<int, 2>> e(m);
        for (auto &[u, v] : e)
            cin >> u >> v;
        vector<int> vis(m), fa(n + 1);
        iota(fa.begin(), fa.end(), 0);
        auto find = [&](auto &find, int x)
        {
            if (x == fa[x])
                return x;
            return fa[x] = find(find, fa[x]);
        };
        for (int i = m - 1; i >= 0; i--)
        {
            auto [u, v] = e[i];
            int fx = find(find, u), fy = find(find, v);
            if (fx == fy)
                vis[i] = 1;
            else
                fa[fx] = fy;
        }
        cout << accumulate(vis.begin(), vis.end(), 0) << '\n';
        for (int i = 0; i < m; i++)
            if (vis[i])
                cout << i + 1 << ' ';
        cout << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 252ms
memory: 6324kb

input:

15
5 7
1 1
1 2
1 3
3 4
3 4
2 4
2 5
9 9
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
100000 0
100000 200000
77128 77528
77919 78319
67747 68147
21468 21468
9500 9500
3099 3099
60221 60222
71712 71713
26587 93317
6972 6972
58270 58271
7190 7190
76105 76106
73929 74329
32751 32751
4 5
35248 35648
4492 96872
160...

output:

3
1 2 4 
3
1 4 7 
0

106620
1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 19 20 21 22 23 26 27 28 29 30 31 33 34 36 39 40 41 42 43 45 46 47 48 52 53 55 56 57 58 59 61 62 63 65 66 68 69 72 73 74 75 77 78 79 80 83 84 85 86 87 88 89 90 91 92 93 94 95 96 98 100 101 103 105 106 107 108 109 110 111 113 114 115 ...

result:

ok 30 lines