1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>

#define LEN 307
#define D (void)

int n, m, k;

int M[LEN][LEN];
int degree[LEN];
int Q[LEN], q = 0;
int entry[LEN];
int kill[LEN];

static inline void qclear()
{
	int i;

	for (i = 0; i < n; ++i) {
		entry[i] = 1;
		kill[i] = 0;
	}

	q = 0;
}

static inline void qpush(int x)
{
	Q[q++] = x;
}

static inline int qpop()
{
	return Q[--q];
}

static inline int qempty()
{
	return q == 0;
}

/**
 * check if d-complicated solution is possible
 */
int possible(int d)
{
	int i, x, e, killed = 0;

	qclear();

	for (i = 0; i < n; ++i) {
		if (degree[i] == 0)
			qpush(i);
	}

	D("checking: %d\n", d);

	while (!qempty()) {
		x = qpop();
		D("visited: %d\n", x + 1);
		e = entry[x];
		if (e > d) { /* this means we need to remove this node */
			kill[x] = 1;
			e = 0;
			killed++;
			D("removed %d\n", x + 1);
		}

		if (killed > k) {
			D("removed %d nodes already\n", killed);
			return 0;
		}

		for (i = 0; i < n; ++i)
			if (M[x][i] && !kill[i] && entry[i] <= e + 1) {
				qpush(i);
				entry[i] = e + 1;
			}
	}

	D("possible!\n");
	return 1;
}

int main()
{
	int i, x, y, s, e;
	scanf("%d%d%d", &n, &m, &k);

	for (x = 0; x < n; ++x) {
		degree[x] = 0;
		for (y = 0; y < n; ++y)
			M[x][y] = 0;
	}

	for (i = 0; i < m; ++i) {
		scanf("%d%d", &x, &y);
		x--; y--;
		M[x][y] = 1;
		degree[y]++;
	}

	s = 0;
	e = n;

	for (i = 0; i < n; ++i) {
		if (possible(i)) {
			printf("%d\n", i);
			break;
		}
	}

	return 0;
}