Задача Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Входные данные. Входной файл содержит числа [latex]n[/latex] [latex]\left(1\leq n\leq 100\right)[/latex] — число вершин в графе и [latex]m[/latex] [latex]\left(1\leq m\leq n*\left(n-1\right)\right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.
Выходные данные. Выведите в выходной файл [latex]n[/latex] пар чисел — для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.
Тесты
| Тесты | Результат | Комментарии |
| 4 41 21 3
2 3 3 4 |
0 21 12 1
1 0 |
пройден |
| 4 1 3 2 |
0 01 00 1
0 0 |
пройден |
Решение
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; int main() { int n, m, a, b; cin >> n >> m; int res[n][2]; for(int i = 0 ; i < n; i++) { res[i][1] = 0; res[i][0] = 0; } for(int i = 0; i < m; i++) { cin >> a >> b; res[b - 1][0]++; res[a - 1][1]++; } for(int i = 0; i < n; i++) { cout << res[i][0] << " " << res[i][1] << endl; } return 0; } |
|
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.io.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a, b; //число вершин графа int n = in.nextInt(); //Число ребер int m = in.nextInt(); int res[][]; //Иницилизация и обнуление двумерного массива // res[номер вершины][0-количество заходов 1-количество исходов] res = new int [n][]; for(int i = 0 ; i < n; i++) { res[i] = new int [2]; res[i][1] = 0; res[i][0] = 0; } // в каждом элементе цикла вводим ребро и для соответствующих вершин увеличиваем счетчик for(int i = 0; i < m; i++) { // ввод ребра графа a-номер вершины исхода b-номер вершины захода a = in.nextInt(); b = in.nextInt(); res[b - 1][0]++; res[a - 1][1]++; } // Вывод в выходной файл n пар чисел - для каждой вершины сначала полустепень захода и затем полустепень исхода. for(int i = 0; i < n; i++) { System.out.printf(Locale.US,"%d %d\n",res[i][0],res[i][1]); } } } |