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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <limits.h>
#include <list>
#include <stack>
#include <vector>
#include <algorithm>
#define NINF INT_MIN
using namespace std;

// Graph is represented using adjacency list
class AdjListNode {
    int v;

public:
    AdjListNode(int _v)
    {
        v = _v;
    }
    int getV() { return v; }
};

// Class to represent a graph using adjacency list
// representation
class Graph {
    int V; // No. of vertices'

    // Pointer to an array containing adjacency lists
    list<AdjListNode>* adj;

public:
    Graph(int V); // Constructor

    // function to add an edge to graph
    void addEdge(int u, int v);

    // Finds longest distances from given source vertex
    int longestPath(std::vector<int>& blacklist);
};

Graph::Graph(int V) // Constructor
{
    this->V = V;
    adj = new list<AdjListNode>[V];
}

void Graph::addEdge(int u, int v)
{
    AdjListNode node(v-1);
    adj[u-1].push_back(node); // Add v to u's list
}

// The function to find longest distances from a given vertex.
// It uses recursive topologicalSortUtil() to get topological
// sorting.
int Graph::longestPath(std::vector<int>& blacklist)
{
    int max = 0;
    int dist[V];

    // Mark all the vertices as not visited
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Initialize distances to all vertices as infinite and
    // distance to source as 0
    for (int i = 0; i < V; i++)
        dist[i] = NINF;

    // Process vertices in topological order
    for(int u = 0; u < V; u++) {
        // Update distances of all adjacent vertices
        list<AdjListNode>::iterator i;
        if (dist[u] == NINF) {
            dist[u] = 0;
        }
        if (dist[u] != NINF) {
            for (i = adj[u].begin(); i != adj[u].end(); ++i) {
                if(std::find(blacklist.begin(), blacklist.end(), i->getV()) != blacklist.end()) {
//                    printf("(%d)", i->getV());
                    continue;
                }
                int possible_max = dist[u] + 1;
                if (dist[u] == 0) {
                    possible_max += 1;
                }
                if (dist[i->getV()] < possible_max) {
                    dist[i->getV()] = possible_max;
                }
                if (possible_max > max) {
                    max = possible_max;
                }
            }
        }
    }

//    for (int i = 0; i < V; i++)
//        printf("%d ", dist[i]);
//    printf("#");
    return max;
}

// Driver program to test above functions
int main()
{
    int n;
    int m;
    int k;
    int u, v;
    scanf("%d %d %d", &n, &m, &k);

    // Create a graph given in the above diagram.
    // Here vertex numbers are 0, 1, 2, 3, 4, 5 with
    // following mappings:
    // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
    Graph g(n);
    for(int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        g.addEdge(u, v);
    }

    std::vector<int> blacklist;
    int max = g.longestPath(blacklist);
    int max_min = max;
    int candidate = 0;
    for (int remove = 0; remove < k; ++remove) {
        for (int i = 0; i < n; ++i) {
            blacklist.push_back(i);
            int change = g.longestPath(blacklist);
            if (change < max_min) {
                max_min = change;
                candidate = i;
                //printf("%d -> %d ", max_min, candidate);
            }
            blacklist.pop_back();
        }
        blacklist.push_back(candidate);
    }
    printf("%d", max_min);

    return 0;
}