Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- using namespace std;
- int main() {
- ifstream in("in.txt");
- ofstream out("out.txt");
- int k, l;
- in >> k >> l;
- int *g = new int [k * l];
- for (int i = 0; i < k; ++i) {
- for (int j = 0; j < l; ++j) {
- in >> g[i * l + j];
- }
- }
- int *matchX = new int[k];
- int *matchY = new int[l];
- bool *visited = new bool[l];
- for (int i = 0; i < k; ++i) {
- matchX[i] = -1;
- }
- for (int j = 0; j < l; ++j) {
- matchY[j] = -1;
- }
- for (int i = 0; i < k; ++i) {
- int current = i;
- for (int s = 0; s < l; ++s) {
- visited[s] = false;
- }
- while (true) {
- int v = -1;
- for (int p = 0; p < l; ++p) {
- if (!visited[p] && g[current * l + p] == 1) {
- v = p;
- break;
- }
- }
- if (v == -1) {
- out << "N\n";
- out << i + 1;
- return 0;
- }
- if (matchY[v] == -1) {
- matchX[current] = v;
- matchY[v] = current;
- break;
- }
- else {
- int next = matchY[v];
- matchX[current] = v;
- matchY[v] = current;
- current = next;
- visited[v] = true;
- }
- }
- }
- for (int j = 0; j < l; ++j) {
- if (matchY[j] == -1) {
- out << "N\n";
- out << k;
- return 0;
- }
- }
- out << "Y\n";
- for (int i = 0; i < k; ++i) {
- out << matchX[i] + 1 << " ";
- }
- in.close();
- out.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement