Ориентированный граф задан списком ребер.
Проверьте, содержит ли он параллельные ребра.
Входные данные
Входной файл содержит числа [latex]n(1\leq n\leq 100)[/latex] — число вершин в графе и [latex]m(1\leq m\leq 10000)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.
Выходные данные
Выведите в выходной файл YES если граф содержит параллельные ребра и NO в противном случае.
Задача на e-olimp. Ссылка на засчитанное решение.
| Входные данные | Выходные данные |
| 3 4 1 2 2 3 1 3 2 1 |
NO |
| 3 4 1 2 2 3 1 3 2 3 |
YES |
Код задачи:
|
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 |
#include <iostream> using namespace std; int main() { int n, m, i = 0, k = 0; bool p = true; cin >> n >> m; int v[m], g[m]; for (int i = 0; i < m; i ++) { cin >> v[i] >> g[i]; } while (p) { for (int j = i+1; j < m; j ++) { if ( (v[i] == v[j]) && (g[i] == g[j]) ) { k++; cout<<"YES"<<endl; p=false; //Выход из цикла. } } i ++; if (i == m) break; //Условие окончания цикла. } if (k == 0) cout<<"NO"<<endl; return 0; } |
Алгоритм решения:
Сначала, добавим пару вершин в разные массивы так, чтоб нулевой элемент массива [latex]v[i][/latex] был началом ребра, а нулевой элемент массива [latex]g[i][/latex] — концом ребра и т.д. После этого в цикле будем сравнивать поочередно пары вершин до тех пор, пока не узнаем, что такая пара вершин уже встречалась, в таком случае выводим YES и завершаем цикл. В противном случае, если наше условие не выполнилось ни разу (т.е. переменная [latex]k[/latex] как была нулем в начале программы, так и осталась) выводим NO.
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Graph { public static void main (String[] args) throws java.lang.Exception { int ii = 0, k = 0; Boolean p = true; Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[] v = new int[m], g = new int[m]; for (int i = 0; i < m; i ++) { v[i] = in.nextInt(); g[i] = in.nextInt(); } while (p) { for (int j = ii+1; j < m; j ++) { if ((v[ii] == v[j]) && (g[ii] == g[j])) { k++; System.out.println("YES"); p=false; //Выход из цикла. } } ii ++; if (ii == m) break; //Условие окончания цикла. } if (k == 0) System.out.println("NO"); } } |
Огромный недостаток e-olymp.com это бедные тесты к многим задачам. В результате такое решение как у Вас не отсекается по времени. Снял баллы за неэффективное решение.
Какие конкретно замечания:
1. Вы проверяете все различные пары ребер. Это квадратичная сложность.
2. Вместо двух вложенных циклов for, Вы делаете один из них циклом while, усложняя восприятие программы
Правильно задача решается прямо во время ввода данных. И даже не требует чтения их до конца если кратное ребро уже встретилось. При таких ограничениях на количество вершин в олимпиадном стиле задача решается так: