Submission #64809354

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define UF_MAX 212345
int uf[UF_MAX];
void uf_init(void) {
  int i;
  for (i = 0; i < UF_MAX; i++) uf[i] = -1;
}
int uf_root(int node) {
  if (uf[node] < 0) return node;
  return uf[node] = uf_root(uf[node]);
}
int uf_size(int node) {
  return -uf[uf_root(node)];
}
int uf_issame(int a, int b) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define UF_MAX 212345

int uf[UF_MAX];

void uf_init(void) {
	int i;
	for (i = 0; i < UF_MAX; i++) uf[i] = -1;
}

int uf_root(int node) {
	if (uf[node] < 0) return node;
	return uf[node] = uf_root(uf[node]);
}

int uf_size(int node) {
	return -uf[uf_root(node)];
}

int uf_issame(int a, int b) {
	return uf_root(a) == uf_root(b);
}

void uf_merge(int a, int b) {
	int ar = uf_root(a);
	int br = uf_root(b);
	if (ar != br) {
		int as = uf_size(ar);
		int bs = uf_size(br);
		if (as <= bs) {
			uf[br] += uf[ar];
			uf[ar] = br;
		} else {
			uf[ar] += uf[br];
			uf[br] = ar;
		}
	}
}

int N, M;
int u[212345], v[212345];

int cnt[212345];
char visited[212345];

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	uf_init();
	for (i = 0; i < M; i++) {
		if (scanf("%d%d", &u[i], &v[i]) != 2) return 1;
		uf_merge(u[i], v[i]);
	}
	/* 連結成分ごとの辺の数を求める */
	for (i = 0; i < M; i++) {
		cnt[uf_root(u[i])]++;
	}
	/* 連結成分ごとに余計な辺の数を足す */
	for (i = 1; i <= N; i++) {
		int r = uf_root(i);
		if (!visited[r]) {
			ans += cnt[r] - (uf_size(r) - 1);
			visited[r] = 1;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result