Submission #73370522

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>
#include <stdlib.h>
int n, m;
int a[114514], b[114514];
int ec[114514], *es[114514];
int rec[114514], *res[114514];
void ae(int f, int t) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = t;
  res[t] = realloc(res[t], sizeof(*res[t]) * (rec[t] + 1));
  if (res[t] == NULL) exit(2);
  res[t][rec[t]++] = f;
}
char visited1[114514];
int order_cnt = 0;
int order[114514];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

int n, m;
int a[114514], b[114514];

int ec[114514], *es[114514];
int rec[114514], *res[114514];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
	res[t] = realloc(res[t], sizeof(*res[t]) * (rec[t] + 1));
	if (res[t] == NULL) exit(2);
	res[t][rec[t]++] = f;
}

char visited1[114514];
int order_cnt = 0;
int order[114514];

void ksb1(int node) {
	int i;
	if (visited1[node]) return;
	visited1[node] = 1;
	for (i = 0; i < ec[node]; i++) {
		ksb1(es[node][i]);
	}
	order[order_cnt++] = node;
}

int ksid = 0;
int ks[114514];

void ksb2(int node) {
	int i;
	if (ks[node]) return;
	ks[node] = ksid;
	for (i = 0; i < rec[node]; i++) {
		ksb2(res[node][i]);
	}
}

int incnt[114514];

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d%d", &n, &m) != 2) return 1;
	for (i = 0; i < m; i++) {
		if (scanf("%d%d", &a[i], &b[i]) != 2) return 1;
		ae(a[i], b[i]);
	}
	for (i = 1; i <= n; i++) {
		ksb1(i);
	}
	for (i = n - 1; i >= 0; i--) {
		if (ks[order[i]] == 0) {
			ksid++;
			ksb2(order[i]);
		}
	}
	for (i = 0; i < m; i++) {
		if (ks[a[i]] != ks[b[i]]) incnt[ks[b[i]]]++;
	}
	for (i = 1; i <= ksid; i++) {
		if (incnt[i] == 0) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

/*

強連結成分分解して、入次数0の頂点を、かつそれのみを選ぶ

強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語
https://manabitimes.jp/math/1250

*/

Submission Info

Judge Result