Задача 5076: Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.
Входные данные
Входной файл содержит числа [latex]n(1 \leq n \leq 100) [/latex] — число вершин в графе и [latex]m(1 \leq m \leq n(n — 1)/2) [/latex] — число ребер. Затем следует [latex]m [/latex] пар чисел — ребра графа.
Выходные данные
Выведите в выходной файл YES если граф является регулярным и NO в противном случае.
Тесты
| Входные данные | Выходные данные |
| 3 3 1 2 1 3 2 3 |
YES |
| 3 2 1 2 2 3 |
NO |
Решение:
Ссылка на ideone C++: http://ideone.com/cCHxvo
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> #include <vector> using namespace std; int main() { int m,n,f,l; bool p=true; cin>>n>>m; vector <int> a(n); for (int i=0; i<m; i++){ cin>>f>>l; a[f-1]++; a[l-1]++; } for (int i=0; i<n; i++){if (a[i]!=a[0]){p=false; break;}} if (p) cout<<"YES"<<endl; else cout<<"NO"<<endl; } |
Ссылка на ideone Java: http://ideone.com/2ih3iK
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int m,n,f,l; boolean p=true; n=in.nextInt(); m=in.nextInt(); int[] a = new int[n]; for (int i=0; i<m; i++){ f=in.nextInt(); l=in.nextInt(); a[f-1]++; a[l-1]++; } for (int i=0; i<n; i++){if (a[i]!=a[0]){p=false; break;}} if (p) System.out.println("YES"); else System.out.println("NO"); } } |
Алгоритм решения: создаем вектор счетчиков, показывающих сколько ребер инцидентно данной вершине. Если все элементы вектора одинаковые, то граф регулярный.
Решение засчитано