5073. Мультиребра

Ориентированный граф задан списком ребер. Проверьте, содержит ли он мультиребра.

Вход. Первая строка содержит количество вершин в графе n (1 ≤ n ≤ 100) и количество ребер m (1 ≤ m ≤ 10000). Затем следует m пар чисел – ребра графа.

Выход. Выведите YES, если граф содержит мультиребра и NO в противном случае.

Пример входа 1	Пример выхода 1
3 4 1 2 2 3 1 3 2 1	NO
Пример входа 2	Пример выхода 2
3 4 1 2 2 3 1 3 2 3	YES

РЕШЕНИЕ

графы

Анализ алгоритма

Пусть g – квадратная матрица размера n, изначально обнулим ее. Для каждого ребра (i, j) увеличим g[i][j] на 1. Поскольку граф ориентированный, то как только значение некоторой ячейки g[i][j] станет больше 1, то в гафе появляется мультиребро.

Пример

Графы, приведенные в примерах, имеют вид:

Реализация алгоритма

Читаем входные данные. Для каждого ребра (i, j) увеличим g[i][j] на 1. Как только в графе появится мультиребро, установим flag = 1.

scanf("%d %d",&n,&m);

memset(g,0,sizeof(g));

flag = 0;

for(i = 0; i < m; i++)

{

scanf("%d %d",&a,&b);

g[a][b]++;

if (g[a][b] > 1) flag = 1;

}

В зависимости от значения переменной flag выводим ответ.

if (flag)

puts("YES");

else

puts("NO");

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

int g[][] = new int[n+1][n+1];

int flag = 0;

for(int i = 0; i < m; i++)

{

int a = con.nextInt();

int b = con.nextInt();

g[a][b]++;

if (g[a][b] > 1) flag = 1;

}

if (flag == 1)

System.out.println("YES");

else

System.out.println("NO");

con.close();

}

}