QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55716 | #4498. Planar Graph | lqhsmash | RE | 0ms | 0kb | C++ | 1.5kb | 2022-10-14 23:01:42 | 2022-10-14 23:01:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6 + 20, M = 2e6 + 20;
int n, m;
bool vis[N], vis_line[M];
vector<int> ans;
struct LINE{
int a, b;
}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++;
}
void dfs(int u, int form){
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i], c = w[i];
if(c == form || vis_line[c]) continue;
if(vis[v]) ans.push_back(c);
vis_line[c] = true;
vis[v] = true;
dfs(v, c);
}
}
void slove(){
for(int i = 1; i <= m; i++){
int a = line[i].a, b = line[i].b;
if(!vis[a]){
vis[a] = true;
dfs(a, i);
}
}
sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for(auto it: ans){
printf("%d ", it);
}
printf("\n");
}
void init(){
ans.clear();
memset(h, -1, sizeof h);
memset(vis, 0, sizeof vis);
memset(vis_line, 0, sizeof vis_line);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int a, b;
scanf("%d%d", &a, &b);
// if(a == b){
// ans.push_back(i);
// }
add(a, b, i);
add(b, a, i);
line[i] = {a, b};
}
}
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: 0
Runtime Error
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 14 15 16 17 19 21 22 23 26 27 28 29 30 31 33 34 39 40 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 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 116 117 118 119...