Ориентированный граф задан списком ребер.
Проверьте, содержит ли он параллельные ребра.
Входные данные
Входной файл содержит числа [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"); } } |