Submission #3590762
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int N;
int *u;
int *u_rank;
}union_find;
union_find *make_union_find(int N){
int i;
union_find *uf = (union_find *)malloc(sizeof(union_find));
uf->N = N;
uf->u = (int *)malloc(sizeof(int) * N);
uf->u_rank = (int *)malloc(sizeof(int) * N);
for(i = 0; i < N; i++){
uf->u[i] = i;
uf->u_rank[i] = 1;
}
return uf;
}
int root_uf(int x, union_find *uf){
int *u = uf->u;
if(u[x] == x){
return x;
}
else{
u[x] = root_uf(u[x], uf);
return u[x];
}
}
void combine_uf(int x, int y, union_find *uf){
int x_root = root_uf(x, uf);
int y_root = root_uf(y, uf);
int *u = uf->u;
int *u_rank = uf->u_rank;
if(x_root == y_root){
return;
}
else if(u_rank[x_root] < u_rank[y_root]){
u[x_root] = y_root;
u_rank[y_root] += u_rank[x_root];
u_rank[x_root] = 0;
}
else{
u[y_root] = x_root;
u_rank[x_root] += u_rank[y_root];
u_rank[y_root] = 0;
}
}
//xとyが同じ集合に属していれば1を,そうでなければ0を返す
int is_same_union_uf(int x, int y, union_find *uf){
if(root_uf(x, uf) == root_uf(y, uf)){
return 1;
}
else{
return 0;
}
}
//xが属する集合の要素数を返す
int rank_uf(int x, union_find *uf){
return uf->u_rank[root_uf(x, uf)];
}
int main(){
int N, M, K, L, r, i, j;
scanf("%d%d", &N, &M);
union_find *uf = make_union_find(N + M);
for(i = 0; i < N; i++){
scanf("%d", &K);
for(j = 0; j < K; j++){
scanf("%d", &L);
L--;
combine_uf(i, N + L, uf);
}
}
r = root_uf(0, uf);
for(i = 0; i < N; i++){
if(root_uf(i, uf) != r){
printf("NO\n");
return 0;
}
}
printf("YES\n");
return 0;
}
Submission Info
Submission Time
2018-11-12 22:39:19+0900
Task
C - Interpretation
User
abc050
Language
C (GCC 5.4.1)
Score
400
Code Size
1729 Byte
Status
AC
Exec Time
20 ms
Memory
1792 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:71:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
./Main.c:74:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &K);
^
./Main.c:76:4: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &L);
^
Judge Result
Set Name
sample
dataset1
dataset2
Score / Max Score
0 / 0
200 / 200
200 / 200
Status
Set Name
Test Cases
sample
sample-01.txt, sample-02.txt
dataset1
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, sample-01.txt, sample-02.txt
Case Name
Status
Exec Time
Memory
01-01.txt
AC
1 ms
128 KB
01-02.txt
AC
1 ms
128 KB
01-03.txt
AC
1 ms
128 KB
01-04.txt
AC
1 ms
128 KB
01-05.txt
AC
1 ms
128 KB
01-06.txt
AC
1 ms
128 KB
01-07.txt
AC
1 ms
128 KB
01-08.txt
AC
1 ms
128 KB
01-09.txt
AC
1 ms
128 KB
01-10.txt
AC
1 ms
128 KB
02-01.txt
AC
14 ms
1024 KB
02-02.txt
AC
18 ms
896 KB
02-03.txt
AC
14 ms
640 KB
02-04.txt
AC
20 ms
1408 KB
02-05.txt
AC
19 ms
896 KB
02-06.txt
AC
19 ms
1408 KB
02-07.txt
AC
20 ms
896 KB
02-08.txt
AC
17 ms
896 KB
02-09.txt
AC
20 ms
1792 KB
02-10.txt
AC
15 ms
896 KB
02-11.txt
AC
15 ms
896 KB
02-12.txt
AC
16 ms
896 KB
02-13.txt
AC
16 ms
896 KB
sample-01.txt
AC
1 ms
128 KB
sample-02.txt
AC
1 ms
128 KB