#include <stdio.h>
#include <string.h>
#define N 100000
#define M 100000
#define L 30
int ds[N], xx[N];
int find(int i) {
int p, r;
if (ds[i] < 0)
return i;
p = ds[i], r = find(p);
xx[i] ^= xx[p];
return r;
}
int join(int i, int j, int x) {
int ri = find(i), rj = find(j);
x ^= xx[i] ^ xx[j], i = ri, j = rj;
if (i == j)
return x;
if (ds[i] > ds[j])
ds[i] = j, xx[i] = x;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, xx[j] = x;
}
return 0;
}
int bb[L];
int get(int x) {
int l, y;
y = 0;
for (l = 0; l < L; l++)
if ((x & 1 << l) != 0) {
y |= 1 << l;
if ((bb[l] & 1 << l) != 0)
x ^= bb[l];
else {
bb[l] = x;
return -y;
}
}
return y;
}
int main() {
static int xx[M], yy[M];
int n, m, h, i, j, k, l;
scanf("%d%d", &n, &m);
memset(ds, -1, n * sizeof *ds);
k = 0;
for (h = 0; h < m; h++) {
int x;
scanf("%d%d%d", &i, &j, &x), i--, j--;
if ((yy[h] = get(xx[h] = join(i, j, x))) < 0)
yy[h] = -yy[h], k++;
}
printf("%d\n", k);
for (l = 0; l < L; l++)
if (bb[l]) {
printf("%d", bb[l]);
k = 0;
for (h = 0; h < m; h++)
if ((yy[h] & 1 << l) != 0)
k++;
printf(" %d", k);
for (h = 0; h < m; h++)
if ((yy[h] & 1 << l) != 0)
printf(" %d", h + 1);
printf("\n");
}
return 0;
}
Compilation message
parkticni.c: In function 'main':
parkticni.c:59:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
parkticni.c:65:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d%d%d", &i, &j, &x), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
58 ms |
3328 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
1560 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
32 ms |
2244 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
54 ms |
3696 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
49 ms |
2940 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
77 ms |
4808 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
55 ms |
4016 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
86 ms |
5672 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
1360 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
59 ms |
4164 KB |
There is a simple cycle which is not good |
2 |
Halted |
0 ms |
0 KB |
- |