Задача:
Дан ориентированный граф. Требуется определить, есть ли в нём цикл.
Технические условия:
Входные данные:
В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда существует ребро, идущее из [latex]i[/latex] -й вершины в [latex]j[/latex]-ю. Гарантируется, что на диагонали матрицы будут стоять нули.
Выходные данные:
Выведите «0«, если в заданном графе цикла нет, и «1«, если он есть.
Результат на С++
Результат на Java
Код на С++:
|
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 43 44 45 46 47 48 |
#include <iostream> using namespace std; int ** a; // Матрица смежности будет записана именно сюда. int n = 51; // Число вершин. int * was;// Массив цвета вершины. bool dfs(int key){ //"Красим" вершину в серый цвет (указываем, что мы в нее вошли). was[key] = 1; //Проходим все связанные с текущей вершиной. for(int i = 0; i < n; i++){ //Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то: if(a[key][i]){ //если вершина "белая" (т. е. мы в неё еще не заходили)- //запускаем рекурсивный вызов DFS от этой вершины. if(was[i] == 0){if(dfs(i)) return true;} //если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)- //мы нашли цикл, следовательно поиск можно завершить. else if(was[i] == 1){ return true;} } } //Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную) was[key] = 2; //и возвращаем результат поиска (мы ничего не нашли). return false; } int main() { cin >> n; a = new int *[n]; was = new int [n]; for(int i = 0; i < n; i++){ a[i] = new int [n]; was[i] = 0; for(int j = 0; j < n; j++){ cin >> a[i][j]; } } for(int i = 0; i < n; i++){ //Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1". //Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь //цикл, даже если вершина покрашена в черный цвет. if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;} } //Если if ни разу не сработал - выводим "0". cout << "0\n"; return 0; } |
Код на Java:
|
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
import java.util.*; import java.lang.*; import java.io.*; class Graphdfs { private int[][] matrix; // Матрица смежности будет записана именно сюда. private int n; // Число вершин. private int[] was;// Массив цвета вершины. public Graphdfs(){} public Graphdfs(int n) { this.n = n; matrix = new int [n][n]; was = new int [n]; } public void setMatrix(Scanner in) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) matrix[i][j] = in.nextInt(); } public void showMatrix() { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { System.out.print(matrix[i][j]); if(j < n - 1) System.out.print(" "); else System.out.println(); } } } public boolean dfs(int key) { was[key] = 1; for(int i = 0; i < n; i++) { if(matrix[key][i] != 0) { if(was[i] == 0){ if(dfs(i)) return true; } else if(was[i] == 1){ return true; } } } was[key] = 2; return false; } public int[] getWas(){ return was; } } public class Main { public static void main (String[] args) throws java.lang.Exception { //System.out.println("ok1"); Scanner in = new Scanner(System.in); //System.out.println("ok2"); int n = in.nextInt(); //System.out.println("ok3"); Graphdfs Graph = new Graphdfs(n); //System.out.println("ok4"); Graph.setMatrix(in); //System.out.println("ok5"); //Graph.showMatrix(); for(int i = 0; i < n; i++){ if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);} } System.out.println(0); } } |
Пояснение:
Циклом в графе называется цепь, в которой первая и последняя вершина совпадает. Значит, если проходя по вершинам графа в лексикографическом порядке, в какой — то момент я попаду в вершину в которую вошел, но еще не вышел, то это будет означать, что я нашёл цикл.
Если б мне по условию давался связный ориентированный граф, то достаточно было бы запустить поиск (поиск в глубину) из произвольной вершины и, по идее, мы бы обошли весь граф. Так как о связности графа ничего сказано не было, пришлось запускать поиск из каждой вершины.
Уточните, пожалуйста, что вы имеете в виду под «по вершинам графа в лексикографическом порядке».
Начинать поиск с каждой вершины излишне. Если предыдущий поиск не дал цикла, то все пройденные вершины ни в какой цикл войти не могут.
Я имел в виду, что я прохожу вершины в цикле от 0 — ой до n-1 — ой, т. е. я прохожу вершины в порядке возрастания их номеров.
Я не мог быть уверен на счет числа компонент связности. По этой причине я не могу запускать поиск только из одной вершины, но я вставил в условие проверку «цвета» данной вершины, таким образом, в цикле программа будет пропускать уже посещенные вершины, а значит отсекать пройденную компоненту связности.
Согласен. Зачтено
Только поправьте:
— вектор was на самом деле просто массив из n элементов (т.е. вектор вам ненужен)
— нужна ссылка на задачу на сайте e-olimp.
— код программы на этой странице и по ссылке в ideone не совпадает
Засчитана Java-версия, 9 баллов. Замечание: ==true писать не нужно, у Вас регресс: на C++ dfs(i), а на Java: Graph.dfs(i) == true