QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56006#4498. Planar GraphGalaxyAC ✓467ms6632kbC++1.3kb2022-10-16 13:51:222022-10-16 13:51:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-16 13:51:25]
  • 评测
  • 测评结果:AC
  • 用时:467ms
  • 内存:6632kb
  • [2022-10-16 13:51:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 20, M = 2e5 + 20;
int n, m, fa[N];
bool vis[M];
struct LINE{
    int u, v, id;
}line[M];

int e[M], ne[M], h[M], w[M], idx;
void add(int u, int v, int c){
    e[idx] = v, ne[idx] = h[u], w[idx] = c, h[u] = idx++;
}

bool cmp(LINE x, LINE y){
    return x.id > y.id;
}

int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void slove(){
    sort(line + 1, line + m + 1, cmp);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++){
        int u = line[i].u, v = line[i].v, id = line[i].id;
        int fau = find(u), fav = find(v);
        if(fau != fav){
            fa[fau] = fav;
            vis[id] = true;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= m; i++){
        if(!vis[i]) cnt++;
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= m; i++){
        if(!vis[i]) printf("%d ", i);
    }
    printf("\n");
}

void init(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        vis[i] = false;
        int u, v;
        scanf("%d%d", &u, &v);
        line[i] = {u, v, i};
    }
}

int main(){
    int T = 1;
    scanf("%d", &T);
    while(T--){
        init();
        slove();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 467ms
memory: 6632kb

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