Задача e-olimp 4000
Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).
Входные данные
В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex] [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.
Выходные данные
Выведите одно число — искомое количество вершин.
Пример:
| Входные данные | Выходные данные |
| 5 1 | 3 |
| 0 1 1 0 0 | |
| 1 0 1 0 0 | |
| 1 1 0 0 0 | |
| 0 0 0 0 1 | |
| 0 0 0 1 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 37 38 39 40 41 42 |
#include <iostream> #include <stack> using namespace std; int main() { int n; int s; cin>>n>>s; s--; int matrix[n][n]; stack<int> st; int counter=1; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>matrix[i][j]; } } for(int j=0;j<n;j++) { if(matrix[s][j] == 1) st.push(j); } matrix[s][s]=1; while(!st.empty()) { int a=st.top(); st.pop(); if(matrix[a][a]!=1) { for(int j=0;j<n;j++) { if(matrix[a][j] == 1) st.push(j); } counter++; matrix[a][a]=1; } } cout<<counter<<endl; } |
|
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 37 38 39 40 41 42 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), s = in.nextInt()-1, counter = 1; int[][] matrix = new int[n][n]; Stack st = new Stack(); for(int i = 0;i < n; i++) { for(int j = 0;j < n; j++) { matrix[i][j] = in.nextInt(); } } for(int j = 0; j < n; j++) { if(matrix[s][j] == 1) st.push(j); } matrix[s][s] = 1; while(!st.empty()) { int a = (int) st.peek(); st.pop(); if(matrix[a][a] != 1) { for(int j = 0; j < n; j++) { if(matrix[a][j] == 1) st.push(j); } counter++; matrix[a][a] = 1; } } System.out.println(counter); } } |
Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex], и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.
Принято