QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56006 | #4498. Planar Graph | Galaxy | AC ✓ | 467ms | 6632kb | C++ | 1.3kb | 2022-10-16 13:51:22 | 2022-10-16 13:51:25 |
Judging History
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