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
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
AC × 2
AC × 12
AC × 27
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