e-olymp 975

26/06/2015 by Сіренко Валерія Сергіївна

Задача:

Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

Входные данные

В первой строке содержится количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

Выходные данные

Вывести искомое максимальное кратчайшее расстояние.

#include <cstdlib>
#include <iostream>
 using namespace std;
 
int main(){
    int n;
    cin >> n;
    int a[n][n];
    long long maxr = 0;
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> a[i][j];
        }
    }
    for( int k=0 ; k<n ; k++ ){
        for( int i=0 ; i<n ; i++ ){
            for( int j=0 ; j<n ; j++ ){
                if(i != j && a[i][k] != -1 && a[k][j] != -1){
                    if(a[i][j] == -1){
                        a[i][j] = a[i][k] + a[k][j];
                    }
                        else
                    {
                        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
                    }
                }
            }
        }
    }
    for( int i=0 ; i<n ; i++ )
    {
        for( int j=0 ; j<n ; j++ )
        {
            if(a[i][j] > maxr) maxr = a[i][j];
        }
    }
    cout << maxr << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int a[n][n];

long long maxr = 0;

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

cin >> a[i][j];

}

for( int k=0 ; k<n ; k++ ){

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

if(i != j && a[i][k] != -1 && a[k][j] != -1){

if(a[i][j] == -1){

a[i][j] = a[i][k] + a[k][j];

}

else

{

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

}

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

{

for( int j=0 ; j<n ; j++ )

{

if(a[i][j] > maxr) maxr = a[i][j];

}

cout << maxr << endl;

}

Задача на e-olimp

Тесты

input	output
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
5 0 5 5 6 -1 -1 0 9 8 4 -1 -1 0 3 8 6 -1 -1 0 5 -1 2 5 6 0	14

Решение:

По алгоритму Флойда (это алгоритм который способствует нахождению кротчайших расстояний между всеми вершинами взвешенного графа, благородя ему мы берем вершину и проверяем если возможно пройти через нее и это будет короче чем идти напрямик, то сохраняем длину пути через эту вершину ) мы проверяем на прочность все связи, иными словами — мы проходим все ребра и проверяем условие. Если существует альтернативный путь от одной вершины к другой, то будет ли он будет короче если да, то мы его заменяем. Таким алгоритмом мы находим все кротчайшие пути через вершины. Но в ответе должен быть максимальный из путей через вершины, поэтому приходится снова пройтись по путям через вершины (но это уже не ребра, а оптимальные длины путей) и найти кратчайший путь максимальной длины.

Related Images:

e-olymp 974. Флойд-1

17/06/2015 by Зелінський Вячеслав Олександрович

974. Флойд-1

Ссылка на засчитанное решение.

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Код программы:

#include <cstdlib>
#include <iostream>

using namespace std;

int **a;

int main()
{
    int n;
    cin >> n;
    a = new int*[n];
    for( int i=0 ; i<n ; i++ )
    {
        a[i] = new int [n];
        for( int j=0 ; j<n ; j++ )
        {
            cin >> a[i][j];
        }
    }
    
    for( int k=0 ; k<n ; k++ )
    {
        for( int i=0 ; i<n ; i++ )
        {
            for( int j=0 ; j<n ; j++ )
            {
                if( i!=j )
                {
                    a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
                }
            }
        }
    }
    
    for( int i=0 ; i<n ; i++ )
    {
        for( int j=0 ; j<n ; j++ )
        {
            cout << a[i][j] << ( j+1 == n ? '\n' : ' ' );
        }
    }
}

#include <cstdlib>

#include <iostream>

using namespace std;

int **a;

int main()

{

int n;

cin >> n;

a = new int*[n];

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

{

a[i] = new int [n];

for( int j=0 ; j<n ; j++ )

{

cin >> a[i][j];

}

for( int k=0 ; k<n ; k++ )

{

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

{

for( int j=0 ; j<n ; j++ )

{

if( i!=j )

{

a[i][j] = min(a[i][j], a[i][k]+a[k][j]);

}

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

{

for( int j=0 ; j<n ; j++ )

{

cout << a[i][j] << ( j+1 == n ? '\n' : ' ' );

}

Считываем число вершин, затем матрицу смежности. Записываем матрицу смежности в массив указателей. Затем для создания матрицы минимальных путей заменяем каждый элемент матрицы на минимум из непосредственного расстояния между вершинами в матрице смежности и расстоянием между ними, проходящим через одну из их общих вершин. Выводим матрицу минимальных путей.

Related Images:

e-olymp 625. Расстояние между вершинами

17/06/2015 by Зелінський Вячеслав Олександрович

Задача с сайта e-olimp № 625.

Ссылка на засчитанное решение.

РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ

Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.

Входные данные

Первая строка входного файла содержит натуральные числа N, M, S и F (N ≤ 5000, M ≤ 100000, 1 ≤ S, F ≤ N, S ≠ F) — количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие M строк содержат по три натуральных числа b_i, e_i и w_i — номера концов i-ого ребра и его вес соответственно (1 ≤b_i, e_i ≤ N, 0 ≤ w_i ≤ 100000).

Выходные данные

Первая строка должна содержать одно натуральное число — вес минимального пути между вершинами S и F. Во второй строке через пробел выведите вершины на кратчайшем пути из S в F в порядке обхода. Если путь из S в F не существует, выведите -1.

Код программы:

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <climits>
using namespace std;

vector <int> marsh;

int main() {
 
	int n, m1;
	cin>>n>>m1;
	if(n<0 || m1<0){
		cout<<"-1";
		return 0;
	}
	int s,f;
	cin>>s>>f;
	if(n==0 || n==1 || s==0 || f==0){ 
		cout<<"-1"<<endl;
		return 0;
	}
	int max;
	int M[m1][3];
	for(int i=0; i<m1 ; i++){
		for(int j=0; j<3 ; j++){
			cin>>M[i][j];
			max=M[0][0];
			if(M[i][j]<0){ 
				m1=i;
				break;
			}
			if(M[i][j]<0 ){
				cout<<"-1";
				return 0;
			}
		}
	}
	for(int i=0; i<m1 ; i++){
		for(int j=0; j<2 ; j++){
			if(M[i][j]>max){ max=M[i][j];}
        }
    }
	n=max;
	int V=n;
	int h[n];  //массив вершин которые принадлежат минимальному пути от s до f
	int a[n];
	int b[n];
	int GR[V][V]; //V
	for(int i=0; i<n ; i++){
		for(int j=0; j<n ; j++){
			GR[i][j]=0;
		}
	}
	//преобразовываю считанные данные  в матрицу смежности между вершинами 
	for(int i=0; i<m1 ; i++){  
		for(int j=0; j<3 ; j++){
			a[i]=M[i][0];
			b[i]=M[i][1];
			GR[a[i]-1][b[i]-1]=M[i][2];
			GR[b[i]-1][a[i]-1]=M[i][2];
		}
	}
	int st=s-1;
	int count, index, i, u, m=st+1;
	long long distance[V];
	bool visited[V];
	for (i=0; i<V; i++){							
		distance[i]=LLONG_MAX; visited[i]=false;
	}
	distance[st]=0;

	long long min;
	
	for (count=0; count<V-1; count++){							
		min=LLONG_MAX;
		for (i=0; i<V; i++)
	        if (!visited[i] && distance[i]<=min){
				min=distance[i]; index=i;
			}
			u=index;
			visited[u]=true;
		for (i=0; i<V; i++){												//V
			if (!visited[i] && GR[u][i] && distance[u]!=LLONG_MAX 
				&& distance[u]+GR[u][i]<distance[i]){
                       distance[i]=distance[u]+GR[u][i];
				       h[i]=u;
			}
		}
	}
	//вывод расстояния
	if(n!=0 && n!=1){
		for (i=0; i<1; i++){
	        if(s>n || f>n ){
				cout<<"-1";
				break;
			}
			if(distance[f-1]==LLONG_MAX){
				cout<<"-1"<<endl;
				break;
			}
			if (distance[i]!=LLONG_MAX  ){
				cout<<distance[f-1]<<endl;
				// вывод маршрута	
				s--;
				f--;
				int c=f;
				while (c!=(s)) {
					marsh.push_back(c+1); 
					c=h[c];
				}
				marsh.push_back(s+1);
				cout << marsh[marsh.size()-1];
				for(int t = marsh.size()-2; t >=0; t--) 
                                        cout << " " << marsh[t];
				        cout << endl;
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <iostream>

#include <vector>

#include <set>

#include <utility>

#include <climits>

using namespace std;

vector <int> marsh;

int main() {

int n, m1;

cin>>n>>m1;

if(n<0 || m1<0){

cout<<"-1";

return 0;

}

int s,f;

cin>>s>>f;

if(n==0 || n==1 || s==0 || f==0){

cout<<"-1"<<endl;

return 0;

}

int max;

int M[m1][3];

for(int i=0; i<m1 ; i++){

for(int j=0; j<3 ; j++){

cin>>M[i][j];

max=M[0][0];

if(M[i][j]<0){

m1=i;

break;

}

if(M[i][j]<0 ){

cout<<"-1";

return 0;

}

for(int i=0; i<m1 ; i++){

for(int j=0; j<2 ; j++){

if(M[i][j]>max){ max=M[i][j];}

}

n=max;

int V=n;

int h[n]; //массив вершин которые принадлежат минимальному пути от s до f

int a[n];

int b[n];

int GR[V][V]; //V

for(int i=0; i<n ; i++){

for(int j=0; j<n ; j++){

GR[i][j]=0;

}

//преобразовываю считанные данные в матрицу смежности между вершинами

for(int i=0; i<m1 ; i++){

for(int j=0; j<3 ; j++){

a[i]=M[i][0];

b[i]=M[i][1];

GR[a[i]-1][b[i]-1]=M[i][2];

GR[b[i]-1][a[i]-1]=M[i][2];

}

int st=s-1;

int count, index, i, u, m=st+1;

long long distance[V];

bool visited[V];

for (i=0; i<V; i++){

distance[i]=LLONG_MAX; visited[i]=false;

}

distance[st]=0;

long long min;

for (count=0; count<V-1; count++){

min=LLONG_MAX;

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

if (!visited[i] && distance[i]<=min){

min=distance[i]; index=i;

}

u=index;

visited[u]=true;

for (i=0; i<V; i++){ //V

if (!visited[i] && GR[u][i] && distance[u]!=LLONG_MAX

&& distance[u]+GR[u][i]<distance[i]){

distance[i]=distance[u]+GR[u][i];

h[i]=u;

}

//вывод расстояния

if(n!=0 && n!=1){

for (i=0; i<1; i++){

if(s>n || f>n ){

cout<<"-1";

break;

}

if(distance[f-1]==LLONG_MAX){

cout<<"-1"<<endl;

break;

}

if (distance[i]!=LLONG_MAX ){

cout<<distance[f-1]<<endl;

// вывод маршрута

s--;

f--;

int c=f;

while (c!=(s)) {

marsh.push_back(c+1);

c=h[c];

}

marsh.push_back(s+1);

cout << marsh[marsh.size()-1];

for(int t = marsh.size()-2; t >=0; t--)

cout << " " << marsh[t];

cout << endl;

}

return 0;

}

После считывания входных данных создаем три массива. Массив вершин входящих в кратчайший путь, а также два массива для преобразования считанной матрицы в матрицу смежности вершин графа. Далее с помощью алгоритма Дейкстра находим кратчайшее расстояние до каждой вершины и одновременно записываем в массив [latex]h\left [ n \right ][/latex] вершины, через которые проходит кратчайший путь. Затем выводим расстояние до вершины [latex]f[/latex] если путь к ней существует, иначе печатаем: «-1». Далее выводим кратчайший маршрут между вершинами [latex]s[/latex] и [latex]f[/latex].

Related Images:

e-olymp 4850. Шайтан-машинка

17/06/2015 by Марченко Філіп Олександрович

Условие

У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.

Ибрагим может нажимать кнопки в любом порядке. Его интересует, как ему получить на табло число [latex]b[/latex] после некоторой последовательности нажатий, если сейчас шайтан-машинка показывает [latex]a[/latex]. Помогите ему найти минимальное необходимое число нажатий.

Входные данные

В одной строке находится два натуральных числа [latex]a[/latex] и [latex]b[/latex] latex[/latex].

Выходные данные

Вывести минимальное необходимое количество действий.

Задача
Зачтённое решение

Код

Ideone

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе
    int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;
    return res;
}

bool was [10000]; //массив использованных вершин.
int vertex[10000]; //подсчёт кол-ва пройденных рёбер..
queue<int> q; //очередь для BFS

//BFS
void bfs (int start, int finish){
    if (start==finish){  //если мы сразу попали в нужную вершину - выходим из программы.
        cout << 0 << endl;
        return;
    }
    else {
        for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1
            vertex[i]=1;
        }
        q.push (start); //будем рассматривать каждую вершину
        was[start] = true;
        while (!q.empty()){
            int tmp = q.front(); //рассматриваемая вершина
            q.pop();
            int tmp1 = tmp;
            tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
            if (!was[tmp1]){
                if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                    q.push(tmp1);
                    vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.
                }
            }
            //действия повторяются для других операций.
            tmp1=tmp;
            tmp1 += sum_n(tmp1);
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
            tmp1=tmp;
            tmp1 -= 2;
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b; //ввод начала и конца
    bfs (a, b);//процедура выполнения
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе

int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;

return res;

}

bool was [10000]; //массив использованных вершин.

int vertex[10000]; //подсчёт кол-ва пройденных рёбер..

queue<int> q; //очередь для BFS

//BFS

void bfs (int start, int finish){

if (start==finish){ //если мы сразу попали в нужную вершину - выходим из программы.

cout << 0 << endl;

return;

}

else {

for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1

vertex[i]=1;

}

q.push (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.empty()){

int tmp = q.front(); //рассматриваемая вершина

q.pop();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.push(tmp1);

vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum_n(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

int main() {

int a, b;

cin >> a >> b; //ввод начала и конца

bfs (a, b);//процедура выполнения

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class ShaitanEngines {
    private static int N = 10001;
    private static boolean [] was = new boolean [N];
    private static int [] vertice = new int [N];
    private static Queue <Integer> q = new LinkedList();
    public static int sum (int n) {
        return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);  
    }
    public static void bfs (int start, int finish) {
        if (start == finish) {
            System.out.println(1);
            return;
        }
        else {
            for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1
                vertice[i]=1;
            }
            q.add (start); //будем рассматривать каждую вершину
            was[start] = true;
            while (!q.isEmpty()){
                int tmp = q.element(); //рассматриваемая вершина
                q.remove();
                int tmp1 = tmp;
                tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
                if (!was[tmp1]){
                    if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                        q.add(tmp1);
                        vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.
                    }
                }
                //действия повторяются для других операций.
                tmp1=tmp;
                tmp1 += sum(tmp1);
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
                tmp1=tmp;
                tmp1 -= 2;
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
            }
        }
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        bfs(a, b);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class ShaitanEngines {

private static int N = 10001;

private static boolean [] was = new boolean [N];

private static int [] vertice = new int [N];

private static Queue <Integer> q = new LinkedList();

public static int sum (int n) {

return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);

}

public static void bfs (int start, int finish) {

if (start == finish) {

System.out.println(1);

return;

}

else {

for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1

vertice[i]=1;

}

q.add (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.isEmpty()){

int tmp = q.element(); //рассматриваемая вершина

q.remove();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.add(tmp1);

vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int a = sc.nextInt();

int b = sc.nextInt();

bfs(a, b);

}

Решение

Для решения данной задачи я решил использовать алгоритм BFS (поиск в ширину). Обычно, данный алгоритм применяется для поиска пути от одной вершины к другой, причём длина пути должна быть минимальной.

Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.

Related Images:

e-olymp 5073. Проверка на наличие параллельных ребер (ОГ)

16/06/2015 by Байков Дмитро

Ориентированный граф задан списком ребер.

Проверьте, содержит ли он параллельные ребра.

Входные данные

Входной файл содержит числа [latex]n(1\leq n\leq 100)[/latex] — число вершин в графе и [latex]m(1\leq m\leq 10000)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

Выходные данные

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

Задача на e-olimp. Ссылка на засчитанное решение.

Входные данные	Выходные данные
3 4 1 2 2 3 1 3 2 1	NO
3 4 1 2 2 3 1 3 2 3	YES

Код задачи:

#include <iostream>
using namespace std;

int main() 
{
	int n, m, i = 0, k = 0;
	bool p = true;
	cin >> n >> m;
	int v[m], g[m];
	for (int i = 0; i < m; i ++)
	{
		cin >> v[i] >> g[i];
	}
	while (p)
	{
		for (int j = i+1; j < m; j ++)
		{
			if ( (v[i] == v[j]) && (g[i] == g[j]) ) 
			{ 
				k++; 
				cout<<"YES"<<endl; 
				p=false; //Выход из цикла.
			}
		}
		i ++;
		if (i == m) break; //Условие окончания цикла.
	}
	if (k == 0) cout<<"NO"<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m, i = 0, k = 0;

bool p = true;

cin >> n >> m;

int v[m], g[m];

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

{

cin >> v[i] >> g[i];

}

while (p)

{

for (int j = i+1; j < m; j ++)

{

if ( (v[i] == v[j]) && (g[i] == g[j]) )

{

k++;

cout<<"YES"<<endl;

p=false; //Выход из цикла.

}

i ++;

if (i == m) break; //Условие окончания цикла.

}

if (k == 0) cout<<"NO"<<endl;

return 0;

}

Ссылка на ideone.

Алгоритм решения:

Сначала, добавим пару вершин в разные массивы так, чтоб нулевой элемент массива [latex]v[i][/latex] был началом ребра, а нулевой элемент массива [latex]g[i][/latex] — концом ребра и т.д. После этого в цикле будем сравнивать поочередно пары вершин до тех пор, пока не узнаем, что такая пара вершин уже встречалась, в таком случае выводим YES и завершаем цикл. В противном случае, если наше условие не выполнилось ни разу (т.е. переменная [latex]k[/latex] как была нулем в начале программы, так и осталась) выводим NO.

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Graph
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int ii = 0, k = 0;
		Boolean p = true;
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int[] v = new int[m], g = new int[m];
		for (int i = 0; i < m; i ++)
		{
			v[i] = in.nextInt();
			g[i] = in.nextInt();
		}
		while (p)
		{
			for (int j = ii+1; j < m; j ++)
			{
				if ((v[ii] == v[j]) && (g[ii] == g[j])) 
				{ 
					k++; 
					System.out.println("YES"); 
					p=false; //Выход из цикла.
				}
			}
			ii ++;
			if (ii == m) break; //Условие окончания цикла.
		}
		if (k == 0) System.out.println("NO"); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Graph

{

public static void main (String[] args) throws java.lang.Exception

{

int ii = 0, k = 0;

Boolean p = true;

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

int[] v = new int[m], g = new int[m];

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

{

v[i] = in.nextInt();

g[i] = in.nextInt();

}

while (p)

{

for (int j = ii+1; j < m; j ++)

{

if ((v[ii] == v[j]) && (g[ii] == g[j]))

{

k++;

System.out.println("YES");

p=false; //Выход из цикла.

}

ii ++;

if (ii == m) break; //Условие окончания цикла.

}

if (k == 0) System.out.println("NO");

}

Related Images:

e-olymp 5072. Подсчет количества ребер (ОГ)

28/05/2015 by Царев Николай Александрович

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

Входные данные

Входной файл содержит число n (1 ≤ n ≤ 100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

Выходные данные

Выведите в выходной файл количество ребер заданного графа.

Решение

Задача на E-Olimp.

30 1 11 0 1

0 1 1

50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

21 11 1

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int k, l=0;
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++){
            cin >> k;
            if(k)
            l++;
        }
    }
    cout << l << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int k, l=0;

for(int i=0;i<n;i++){

for(int j=0; j<n; j++){

cin >> k;

if(k)

l++;

}

cout << l << endl;

return 0;

}

Алгоритм решения прост. Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем если 1, и выводим ответ.

Задача на ideone

Related Images:

e-olymp 976. Флойд — существование

14/05/2015 by Осецимський Анатолій Вадимович

По некоторым причинам в статье рассматриваются две близкие задачи. Приведенный программный код содержит все необходимые функции, для решения обеих. Вставляя или убирая комментарии в строках 129, 130 можно выбрать, какую из задач будет решать программа.

e-olymp 974. Флойд 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Пройденный тесты.

e-olymp 976. Флойд — существование

Дан ориентированный взвешенный граф. По его матрице смежности необходимо для каждой пары вершин определить, существует кратчайший путь между ними или нет.

Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути.
Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

#include <iostream>
#include <vector>
#include <deque>  
using namespace std;

struct vertax{ // структура вершина
	int vert, index, father; bool visited;
	vertax(int a){vert = a; index = 10001; father = a;visited = false;}
	vertax(int a, int b){
		vert = a;
		father = b;
		index = 10001;visited = false;
	}
	vertax(int a, int b, int x){
		vert = a;
		father = b;
		index = x;visited = false;
	}
	vector<vertax> follow;// с кем связанна эта вершина
	~vertax(){}
};

struct graph{
	vector<vertax> v; // list of vertax
	int count;
	graph(){};
	graph(int n){
		count = n;
	}
	void get(){//инициализируем граф
		for(int i = 1; i <= count; i++){
			vertax v(i);
			for(int j = 1; j <= count; j++){
				int x;
				cin >> x;
				if(x != 0){
					vertax temp(j, i, x);
					v.follow.push_back(temp);
				}
			}
			graph::v.push_back(v);
		}
	}
	void write(){//вывод вершины, и с кем она связанна
		for(int i = 0; i < count; i++){
			cout << v[i].index << ":";
			for(int j = 0; j < v[i].follow.size(); j++){
				cout << v[i].follow[j].vert << " ";
			}
			cout << endl;
		}
	}
	void way(vertax& x){//алгоритм
		deque<vertax> list;
		x.index = 0;
		x.visited = true;
		list.push_front(x);
		while(!list.empty()){
			vertax& y = list[0];
			for(int i = 0; i < y.follow.size();i++){
				v[y.follow[i].vert -1].visited = true;
				if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){
					v[y.follow[i].vert-1].index = y.index+y.follow[i].index;
					if(v[y.follow[i].vert-1].index > -102){
						list.push_back(v[y.follow[i].vert-1]);
					}
				}
			}
			list.pop_front();
		}
	}
	void def(){//фунция к приведению значений по умолчанию
		for(int i = 0; i < v.size(); i++){
			v[i].index = 10001;
			v[i].visited = false;
		}
	}
	void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else if(v[j].index < -50){
					cout << 2 << " ";
				}else{
					cout << 1 << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else if(v[v.size()-1].index < -50){
					cout << 2 ;
				}else{
					cout << 1 ;
				}
			def();
			cout << endl;
		}
	}
	void task2(){ // Решение задачи e-olymp.com №974: Флойд-1
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else{
					cout << v[j].index << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else{
					cout << v[v.size()-1].index;
				}
			def();
			cout << endl;
		}
	}
};


int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	graph dog(n);
	dog.get();
	dog.task1();// Решаем задачу №976: Флойд - существование
	dog.task2();// Решаем задачу №974: Флойд-1
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <vector>

#include <deque>

using namespace std;

struct vertax{ // структура вершина

int vert, index, father; bool visited;

vertax(int a){vert = a; index = 10001; father = a;visited = false;}

vertax(int a, int b){

vert = a;

father = b;

index = 10001;visited = false;

}

vertax(int a, int b, int x){

vert = a;

father = b;

index = x;visited = false;

}

vector<vertax> follow;// с кем связанна эта вершина

~vertax(){}

};

struct graph{

vector<vertax> v; // list of vertax

int count;

graph(){};

graph(int n){

count = n;

}

void get(){//инициализируем граф

for(int i = 1; i <= count; i++){

vertax v(i);

for(int j = 1; j <= count; j++){

int x;

cin >> x;

if(x != 0){

vertax temp(j, i, x);

v.follow.push_back(temp);

}

graph::v.push_back(v);

}

void write(){//вывод вершины, и с кем она связанна

for(int i = 0; i < count; i++){

cout << v[i].index << ":";

for(int j = 0; j < v[i].follow.size(); j++){

cout << v[i].follow[j].vert << " ";

}

cout << endl;

}

void way(vertax& x){//алгоритм

deque<vertax> list;

x.index = 0;

x.visited = true;

list.push_front(x);

while(!list.empty()){

vertax& y = list[0];

for(int i = 0; i < y.follow.size();i++){

v[y.follow[i].vert -1].visited = true;

if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){

v[y.follow[i].vert-1].index = y.index+y.follow[i].index;

if(v[y.follow[i].vert-1].index > -102){

list.push_back(v[y.follow[i].vert-1]);

}

list.pop_front();

}

void def(){//фунция к приведению значений по умолчанию

for(int i = 0; i < v.size(); i++){

v[i].index = 10001;

v[i].visited = false;

}

void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование

for(int i = 0; i < v.size(); i++){

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else if(v[j].index < -50){

cout << 2 << " ";

}else{

cout << 1 << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else if(v[v.size()-1].index < -50){

cout << 2 ;

}else{

cout << 1 ;

}

def();

cout << endl;

}

void task2(){ // Решение задачи e-olymp.com №974: Флойд-1

for(int i = 0; i < v.size(); i++){

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else{

cout << v[j].index << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else{

cout << v[v.size()-1].index;

}

def();

cout << endl;

}

};

int main() {

ios::sync_with_stdio(false);

int n;

cin >> n;

graph dog(n);

dog.get();

dog.task1();// Решаем задачу №976: Флойд - существование

dog.task2();// Решаем задачу №974: Флойд-1

return 0;

}

link

Related Images:

e-olymp 4853. Кратчайший путь

13/05/2015 by Осецимський Анатолій Вадимович

Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.

Условие задачи на e-olimp.
Cсылка на пройденный тесты.

Раз нам надо найти кратчайший путь путь, то будем использовать BFS- поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства я использовал вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор «graf», выступающий в роли графа, причем мы добавляем сразу к вершинам ([latex] graf[x].push_back(y);[/latex]) то есть [latex] x[/latex] — ая вершина получает связь с вершиной [latex] y[/latex], и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем — нибудь, если да, что работаем [latex] while [/latex] — ом, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция [latex] bfs[/latex] вернет [latex] 1[/latex], что запустит тело [latex] if [/latex]- а и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор [latex] family[/latex], в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла [latex] i [/latex] -ая вершина). Восстановленный путь записываем в вектор [latex] ans[/latex]. После чего [latex] while[/latex] прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим [latex]-1[/latex], иначе выводим количество вершин, участвующих в построении пути и сам путь.

link.

#include <iostream>
#include <vector>
using namespace std;

int n,m,a,b,count = 0;
vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные
    count++;
    if(beg == end){
        ok = true;
        return 1;
    }else{
        for(int i = graf[beg].size() - 1;i >= 0;i--){
            if(!popa[graf[beg][i]]){
                ver.push_back(graf[beg][i]);
                family.push_back(beg);
                popa[graf[beg][i]] = true;
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> a >> b;
    for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов
            graf.push_back(ans);
            popa.push_back(false);
    }
    ver.push_back(a);family.push_back(a);
    for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна 
        int x,y;
        cin >> x >> y;
        if(x != y){ // проверка на петлю
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
    }
    if(!graf[a].empty()){ //если вершины начала не изолированна 
        while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"
            if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути
                count--;// Нам надо начать с последней вершины,а это count - 1 вершина
                int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины
                ans.push_back(b);//вектор ответа
                while(ver[count] != a){ // пока не дошли до начальной вершины
                    while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА
                        p++;
                    }
                    ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)
                    count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины 
                    p = 1;
                }
            }
        }
        if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)
            cout << ans.size()-1 << endl;
            for(int i = ans.size()-1; i >= 0; i--){
                cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии
            }
        }else{ // иначе -1
            cout << "-1\n";
        }
    }else{//если начальная вершина изолирована,то сразу выводим -1
        cout << "-1\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m,a,b,count = 0;

vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные

count++;

if(beg == end){

ok = true;

return 1;

}else{

for(int i = graf[beg].size() - 1;i >= 0;i--){

if(!popa[graf[beg][i]]){

ver.push_back(graf[beg][i]);

family.push_back(beg);

popa[graf[beg][i]] = true;

}

return 0;

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

cin >> a >> b;

for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов

graf.push_back(ans);

popa.push_back(false);

}

ver.push_back(a);family.push_back(a);

for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна

int x,y;

cin >> x >> y;

if(x != y){ // проверка на петлю

graf[x].push_back(y);

graf[y].push_back(x);

}

if(!graf[a].empty()){ //если вершины начала не изолированна

while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"

if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути

count--;// Нам надо начать с последней вершины,а это count - 1 вершина

int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины

ans.push_back(b);//вектор ответа

while(ver[count] != a){ // пока не дошли до начальной вершины

while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА

p++;

}

ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)

count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины

p = 1;

}

if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)

cout << ans.size()-1 << endl;

for(int i = ans.size()-1; i >= 0; i--){

cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии

}

}else{ // иначе -1

cout << "-1\n";

}

}else{//если начальная вершина изолирована,то сразу выводим -1

cout << "-1\n";

}

return 0;

}

Related Images:

e-olymp 5076. Регулярный граф

12/05/2015 by Калачьов Андрій Сергійович

Задача 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

#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;
}

#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

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");
    }
}

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");

}

Алгоритм решения: создаем вектор счетчиков, показывающих сколько ребер инцидентно данной вершине. Если все элементы вектора одинаковые, то граф регулярный.

Related Images:

e-olimp 4650. Граф-Турнир

08/05/2015 by Іванов Вячеслав Володимирович

Граф-турнир.

Постановка задачи

Построить на n вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.

Алгоритм решения

Условию удовлетворяет любая тройка вершин, принадлежащих циклу длины три, следовательно, искомый граф сильно связен. Уместно взять за основу полный неориентированный граф [latex]K_n[/latex] (не ограничивая общности рассуждений, будем представлять граф на плоскости как правильный [latex]n[/latex]-угольник) и задать на нём ориентацию рёбер согласно набору правил:

Контур графа (рёбра вида [latex](k, k+1)[/latex]) ориентирован по часовой стрелке.
В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_{i}[/latex], рассматриваемой на данном шаге — [latex]V_{k}[/latex] Если ребро [latex]\left(V_{i}, V_{k}\right)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex]\left[V_{i}, V_{k}\right][/latex], иначе — [latex]\left[V_{k}, V_{i}\right][/latex].

Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация

ideone: http://ideone.com/XwY7fX
Засчитанное решение: http://codeforces.ru/contest/323/submission/10850799
Для решения задачи достаточно хранить граф в форме матрицы смежности.

#include <cstdio>
unsigned G[1000][1000];
int main()
{
    unsigned n; scanf("%u", &n);
    if(n == 4){
        puts("-1");
    }
    else{
	    for(size_t i = 0; i < n; i++){
	        G[i][(i+1)%n] = 1;
	    }
	    for(size_t i = 0; i < n; i++){
	        for(size_t j = 0; j < n; j++){
	            if(G[i][j] + G[j][i] == 0 && i != j){
	                if(i % 2 == j % 2)
	                    G[i][j] = 1;
	                else
	                    G[j][i] = 1;
	            }
	        }
	    }
	    for(size_t i = 0; i < n; i++){
	        for(size_t j = 0; j < n-1; j++){
	            printf("%u ", G[i][j]);
	        }
	        printf("%u\n", G[i][n-1]);
	    }
    }
    return 0;
}

#include <cstdio>

unsigned G[1000][1000];

int main()

{

unsigned n; scanf("%u", &n);

if(n == 4){

puts("-1");

}

else{

for(size_t i = 0; i < n; i++){

G[i][(i+1)%n] = 1;

}

for(size_t i = 0; i < n; i++){

for(size_t j = 0; j < n; j++){

if(G[i][j] + G[j][i] == 0 && i != j){

if(i % 2 == j % 2)

G[i][j] = 1;

else

G[j][i] = 1;

}

for(size_t i = 0; i < n; i++){

for(size_t j = 0; j < n-1; j++){

printf("%u ", G[i][j]);

}

printf("%u\n", G[i][n-1]);

}

return 0;

}

ideone: http://ideone.com/eBcMcY

import java.util.*;
import java.io.*;
import java.math.*;
 
class Solver {	
    public static void main(String args[]) throws IOException{
    	new Solver().run();
	}

	StreamTokenizer in;
	PrintWriter out;

	int nextInt() throws IOException{
		in.nextToken();
		return (int)in.nval;
	}
	void run() throws IOException{
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		out = new PrintWriter(new OutputStreamWriter(System.out));
		solve();
		out.flush();
	}
	void solve() throws IOException{
		int n = nextInt();
    	int[][] G = new int[n][n];
    	if(n == 4)
    		out.println("-1");
    	else{
    		for(int i = 0; i < n; i++)
    			G[i][(i+1)%n] = 1;
    		for(int y = 0; y < n; y++){
    			for(int x = 0; x < n; x++){
    				if(G[y][x] + G[x][y] == 0 && x != y){
    					if(y % 2 == x % 2) G[y][x] = 1;
    					else G[x][y] = 1;
    				}
    			}
    		}
    		for(int y = 0; y < n; y++){
    			for(int x = 0; x < n-1; x++){
    				out.print(G[y][x]);
    				out.print(" ");
    			}
    			out.println(G[y][n-1]);
    		}
    	}
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Solver {

public static void main(String args[]) throws IOException{

new Solver().run();

}

StreamTokenizer in;

PrintWriter out;

int nextInt() throws IOException{

in.nextToken();

return (int)in.nval;

}

void run() throws IOException{

in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

out = new PrintWriter(new OutputStreamWriter(System.out));

solve();

out.flush();

}

void solve() throws IOException{

int n = nextInt();

int[][] G = new int[n][n];

if(n == 4)

out.println("-1");

else{

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

G[i][(i+1)%n] = 1;

for(int y = 0; y < n; y++){

for(int x = 0; x < n; x++){

if(G[y][x] + G[x][y] == 0 && x != y){

if(y % 2 == x % 2) G[y][x] = 1;

else G[x][y] = 1;

}

for(int y = 0; y < n; y++){

for(int x = 0; x < n-1; x++){

out.print(G[y][x]);

out.print(" ");

}

out.println(G[y][n-1]);

}

Related Images:

e-olimp 5075

30/04/2015 by Денисова Ольга

Задача Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Входные данные. Входной файл содержит числа [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

пройден

Решение

#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;
}

#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;

}

Решение на Java:

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]); 
		}
	}
}

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]);

}

Related Images:

e-olimp 4000. Обход в глубину

30/04/2015 by Ковальський Олександр Дмитрович

Задача 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

Решение

#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;
	}

#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;

}

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);
	}
}

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). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

Засчитанное решение.

Related Images:

e-olimp 5077. Полуполный граф

27/04/2015 by Бронфен-Бова Роман

Задача: Полуполный граф

Решение

ссылка на ideone, засчитанное решение на e-olymp

#include<iostream>
using namespace std;

bool used[101][101];

int main(){
  int n, m; cin >> n >> m;
  for(int i = 0; i < m; i++){
     int a,b; cin >> a >> b;
     used[a][b] = used[b][a] = 1;
  }
  for(int i = 1; i <= n; i++){
     for(int j = i+1; j <= n; j++){
        if(used[i][j] == false){
           cout << "NO\n";
           return 0;
        }
     }
  }
  cout << "YES\n";
  return 0;
}

#include<iostream>

using namespace std;

bool used[101][101];

int main(){

int n, m; cin >> n >> m;

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

int a,b; cin >> a >> b;

used[a][b] = used[b][a] = 1;

}

for(int i = 1; i <= n; i++){

for(int j = i+1; j <= n; j++){

if(used[i][j] == false){

cout << "NO\n";

return 0;

}

cout << "YES\n";

return 0;

}

Решение на Java

ссылка на ideone, засчитанное решение на e-olymp

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	static boolean[][] used = new boolean[101][101];
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		for(int i = 0; i < m; i++){
	     	int a, b;
	     	a = sc.nextInt();
	     	b = sc.nextInt();
	    	used[a][b] = used[b][a] = true;
	  	}
		for(int i = 1; i <= n; i++){
	    	for(int j = i+1; j <= n; j++){
	    		if(used[i][j] == false){
	    			System.out.println("NO");
	           		return;
	        	}
	    	}
	  	}
	  	System.out.println("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static boolean[][] used = new boolean[101][101];

static Scanner sc = new Scanner(System.in);

public static void main (String[] args) throws java.lang.Exception

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

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

int a, b;

a = sc.nextInt();

b = sc.nextInt();

used[a][b] = used[b][a] = true;

}

for(int i = 1; i <= n; i++){

for(int j = i+1; j <= n; j++){

if(used[i][j] == false){

System.out.println("NO");

return;

}

System.out.println("YES");

}

Идея решения

Считаем что граф неорентированный и проверяем, не полный ли наш граф. Если полный — выводим «YES», иначе «NO».

Related Images:

e-olimp 4856. Кратчайший путь

24/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

Входные данные

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

Выходные данные

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

Код программы:

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

for (int i=0; i<G[v].size(); i++) {

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

cout << ans[ans.size()-1];

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

Для решения использовался алгоритм Дейкстры, подробнее в комментариях к коду.

Related Images:

e-olimp 122. Горные маршруты

02/04/2015 by Вустянюк Ігор Дмитрович

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу

Пояснение к решению

Поиск путей представляет из себя модифицированный обход в глубину. Вместо массива «глобально посещённых» вершин, в которые уже нельзя возвращаться при обходе, я использую массив «локально посещённых» вершин. Это позволяет использовать одну и ту же вершину в разных, в том числе очень длинных и извращённых путях (в стандартном варианте ищется кратчайший путь, а нам нужны все: в том числе длинные и извращённые).

Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).

Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».

Стоит отметить, что в общем случае задача поиска всех простых путей (пусть даже удовлетворяющих определённым условиям, как в данной задаче) является NP-полной, т.е. решается исключительно переборными алгоритами, работающими за неполиномиальное время (более эффективных алгоритмов для решения таких задач на сегодняшний день неизвестно; кто их найдёт, получит миллион долларов; я не нашёл). Также отметим, что простая модификация приведённого алгоритма позволяет не только вычислять количество простых путей указанной длины, но и перечислять их.

Решение на С++

#include <stdio.h>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Graph {
	vector< vector<int> > AdjList;
	int Size;
	
	Graph(int n) {
		vector<int> List;
		for (int k = 0; k < n; k++)
			AdjList.push_back(List);
		Size = n;
	}

	void add_vertex() {					// вершина == целое число == номер этой вершины в списке вершин
		Size++;
		vector<int> List;
		AdjList.push_back(List);
	}
	
	void add_edge(int u, int v) {		// u и v уже должны быть в списке вершин
		AdjList[u].push_back(v);
	}

	int simple_paths(int start, int end, int max_depth) {
		bool* on_path = (bool*) calloc(Size, sizeof(bool));
		int cur_depth = 0;
		int count = 0;
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count;
	}
	
	void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {
		if (cur_depth <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count++;
			else
				for (int k = 0; k < AdjList[start].size(); k++) {
					int v = AdjList[start][k];
					if (!on_path[v]) {
						cur_depth++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth--;
					}
				}
		}
	}
	
};


int main() {
	int n, k, a, b, d, tmp1, tmp2;
	scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);
	Graph G(n);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		G.add_edge(tmp1 - 1, tmp2 - 1);
	}
	printf("%d\n", G.simple_paths(a-1, b-1, d));
	return 0;
}

#include <stdio.h>

#include <vector>

#include <stdlib.h>

using namespace std;

struct Graph {

vector< vector<int> > AdjList;

int Size;

Graph(int n) {

vector<int> List;

for (int k = 0; k < n; k++)

AdjList.push_back(List);

Size = n;

}

void add_vertex() { // вершина == целое число == номер этой вершины в списке вершин

Size++;

vector<int> List;

AdjList.push_back(List);

}

void add_edge(int u, int v) { // u и v уже должны быть в списке вершин

AdjList[u].push_back(v);

}

int simple_paths(int start, int end, int max_depth) {

bool* on_path = (bool*) calloc(Size, sizeof(bool));

int cur_depth = 0;

int count = 0;

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count;

}

void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {

if (cur_depth <= max_depth) {

on_path[start] = true;

if (start == end)

count++;

else

for (int k = 0; k < AdjList[start].size(); k++) {

int v = AdjList[start][k];

if (!on_path[v]) {

cur_depth++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth--;

}

};

int main() {

int n, k, a, b, d, tmp1, tmp2;

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

Graph G(n);

for (int i = 0; i < k; i++) {

scanf("%d %d", &tmp1, &tmp2);

G.add_edge(tmp1 - 1, tmp2 - 1);

}

printf("%d\n", G.simple_paths(a-1, b-1, d));

return 0;

}

Решение на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class myInt {
	int v;
	public myInt(int a) {
		this.v = a;
	}
}

class Graph {
	Vector<Vector<Integer>> AdjList;

	public Graph(int n) {
		AdjList = new Vector<Vector<Integer>>(n);
		for (int k = 0; k < n; k++)
			AdjList.add(new Vector<Integer>());
	}
	
	public void add_vertex() {
		AdjList.add(new Vector<Integer>());
	}
	
	public void add_edge(int u, int v) {
		AdjList.elementAt(u).add(v);
	}
	
	public int simple_paths(int start, int end, int max_depth) {
		boolean[] on_path = new boolean[AdjList.size()];
		myInt cur_depth = new myInt(0);
		myInt count = new myInt(0);
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count.v;
	}
	
	public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {
		if (cur_depth.v <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count.v++;
			else
				for (int k = 0; k < AdjList.elementAt(start).size(); k++) {
					int v = AdjList.elementAt(start).elementAt(k);
					if (!on_path[v]) {
						cur_depth.v++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth.v--;
					}
				}
		}
	}
}

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();
		int tmp1, tmp2;
		Graph G = new Graph(n);
		for (int i = 0; i < k; i++) {
			tmp1 = in.nextInt();
			tmp2 = in.nextInt();
			G.add_edge(tmp1 - 1, tmp2 - 1);
		}
		System.out.println(G.simple_paths(a-1, b-1, d));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class myInt {

int v;

public myInt(int a) {

this.v = a;

}

class Graph {

Vector<Vector<Integer>> AdjList;

public Graph(int n) {

AdjList = new Vector<Vector<Integer>>(n);

for (int k = 0; k < n; k++)

AdjList.add(new Vector<Integer>());

}

public void add_vertex() {

AdjList.add(new Vector<Integer>());

}

public void add_edge(int u, int v) {

AdjList.elementAt(u).add(v);

}

public int simple_paths(int start, int end, int max_depth) {

boolean[] on_path = new boolean[AdjList.size()];

myInt cur_depth = new myInt(0);

myInt count = new myInt(0);

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count.v;

}

public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {

if (cur_depth.v <= max_depth) {

on_path[start] = true;

if (start == end)

count.v++;

else

for (int k = 0; k < AdjList.elementAt(start).size(); k++) {

int v = AdjList.elementAt(start).elementAt(k);

if (!on_path[v]) {

cur_depth.v++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth.v--;

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), k = in.nextInt();

int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();

int tmp1, tmp2;

Graph G = new Graph(n);

for (int i = 0; i < k; i++) {

tmp1 = in.nextInt();

tmp2 = in.nextInt();

G.add_edge(tmp1 - 1, tmp2 - 1);

}

System.out.println(G.simple_paths(a-1, b-1, d));

}

Related Images:

e-olimp 1667. Конденсация графа

29/03/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

Входные данные

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

Выходные данные

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

Код программы:

#include <iostream>
#include <vector>
using namespace std;

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

for (int i=0; i<n; i++) {

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

for (int i=0; i<n; i++) {

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

Алгоритм решения

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

Научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из графа вершины первой выделенной компоненты, мы снова найдём среди оставшихся вершину с наибольшим временем выхода, снова запустим из неё этот обход, и так далее.

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

e-olimp 4004. Есть ли цикл?

22/03/2015 by Карташов Денис Геннадійович

Задача:

Дан ориентированный граф. Требуется определить, есть ли в нём цикл.

Технические условия:

Входные данные:

В первой строке вводится натуральное число [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

Код на С++:

#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;
}

#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:

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);
	}
}

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);

}

Пояснение:

Циклом в графе называется цепь, в которой первая и последняя вершина совпадает. Значит, если проходя по вершинам графа в лексикографическом порядке, в какой — то момент я попаду в вершину в которую вошел, но еще не вышел, то это будет означать, что я нашёл цикл.

Если б мне по условию давался связный ориентированный граф, то достаточно было бы запустить поиск (поиск в глубину) из произвольной вершины и, по идее, мы бы обошли весь граф. Так как о связности графа ничего сказано не было, пришлось запускать поиск из каждой вершины.

Related Images:

e-olimp 553. Рекурсия

20/03/2015 by Бронфен-Бова Роман

Задача: Рекурсия

Решение

ссылка на ideone, засчитанное решение на e-olimp

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;

map<string,set<string>> G;
map<string,bool> used;
map<string,bool> rec;
vector<string> V;

void dfs(string cur, string aim){
   if(used[cur] || rec[aim]) return;
   used[cur] = 1;
   for(auto i = G[cur].begin(); i != G[cur].end(); i++){
      if(*i != aim){
         dfs(*i,aim);
      }else{
         rec[aim] = 1;
         return;
      }
   }
}

int main(){
   //input
   int n; cin >> n;
   for(int i = 0; i < n; i++){
      string curVert; cin >> curVert;
      V.push_back(curVert);
      int m; cin >> m;
      while(m--){
         string inp; cin >> inp;
         G[curVert].insert(inp);
      }
      if(i != n-1){
         string stars;
         cin >> stars;
      }
   }
   //work
   for(auto i : V){
      dfs(i, i);
      used.clear();
   }
   for(auto i : V){
      cout << i << (rec[i] ? ": YES" : ": NO") << endl;
   }
   return 0;
}

#include<iostream>

#include<vector>

#include<set>

#include<map>

#include<string>

using namespace std;

map<string,set<string>> G;

map<string,bool> used;

map<string,bool> rec;

vector<string> V;

void dfs(string cur, string aim){

if(used[cur] || rec[aim]) return;

used[cur] = 1;

for(auto i = G[cur].begin(); i != G[cur].end(); i++){

if(*i != aim){

dfs(*i,aim);

}else{

rec[aim] = 1;

return;

}

int main(){

//input

int n; cin >> n;

for(int i = 0; i < n; i++){

string curVert; cin >> curVert;

V.push_back(curVert);

int m; cin >> m;

while(m--){

string inp; cin >> inp;

G[curVert].insert(inp);

}

if(i != n-1){

string stars;

cin >> stars;

}

//work

for(auto i : V){

dfs(i, i);

used.clear();

}

for(auto i : V){

cout << i << (rec[i] ? ": YES" : ": NO") << endl;

}

return 0;

}

Идея решения

Можно заметить, что каждая процедура — это вершина ориентированного графа. Чтобы узнать, является ли процедура потенциально рекурсивной, нужно было запустить из неё поиск в глубину и узнать, сможем ли мы прийти к ней вновь.

Было решено использовать map<string,set<string>> как структуру для описания графа: каждая вершина — это строка и у каждой вершины есть множество вершин (строк), смежных с ней.
А еще задача имеет классификацию — поиск в глубину, что как бы намекает.

Related Images:

Skynet: the Virus

14/10/2014 by Бронфен-Бова Роман

SKYNET FINALE — LEVEL 1

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз, нам нужна ваша помощь. СТОП

Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

N — Количество узлов, включая шлюзы
L — Количество связей
E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N; //Количество узлов, включая шлюзы
    int L; //Количество связей
    int E; //Количество шлюзов
    cin >> N >> L >> E; cin.ignore();
    
    int N1[L][2]; // Массив для связей
    for (int i = 0; i < L; i++) {
        cin >> N1[i][0] >> N1[i][1]; cin.ignore();
    }
    
    int EI[E]; // Индексы шлюзов
    for (int i = 0; i < E; i++) {
        cin >> EI[i]; cin.ignore();
    }
    
    // Алгоритм сортировки (его достаточно)
    for(int i = 0; i < L; i++){
        for(int k =0; k < E; k++){
            if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);
        }
    }

    // игровой цикл
    while (1) {
        int SI; //Индекс связи, на которой находится Агент
        cin >> SI; cin.ignore();

        bool AgentIsNear = false; //Агент возле шлюза!
        
        for(int i = 0; i < L; i++){
            bool T = false; //Для прерывания цикла
            for(int k = 0; k < E; k++){
                if(EI[k] == N1[i][0] && SI == N1[i][1]){
                    cout << EI[k] << ' ' << SI << endl;
                    N1[i][0] = -1;
                    AgentIsNear = true;
                    T = true;
                    break;
                }
            }
            if(T) break;
        }
        
        if(!AgentIsNear){
            for(int i = 0; i < L; i++){
                bool T = false; //Для прерывания цикла
                for(int k = 0; k < E; k++){
                    if(N1[i][0] == EI[k]){
                        cout << EI[k] << ' ' << N1[i][1] << endl;
                        N1[i][0] = -1;
                        T = true;
                        break;
                    }
                }
                if(T) break;
            }
        }
        
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int N; //Количество узлов, включая шлюзы

int L; //Количество связей

int E; //Количество шлюзов

cin >> N >> L >> E; cin.ignore();

int N1[L][2]; // Массив для связей

for (int i = 0; i < L; i++) {

cin >> N1[i][0] >> N1[i][1]; cin.ignore();

}

int EI[E]; // Индексы шлюзов

for (int i = 0; i < E; i++) {

cin >> EI[i]; cin.ignore();

}

// Алгоритм сортировки (его достаточно)

for(int i = 0; i < L; i++){

for(int k =0; k < E; k++){

if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);

}

// игровой цикл

while (1) {

int SI; //Индекс связи, на которой находится Агент

cin >> SI; cin.ignore();

bool AgentIsNear = false; //Агент возле шлюза!

for(int i = 0; i < L; i++){

bool T = false; //Для прерывания цикла

for(int k = 0; k < E; k++){

if(EI[k] == N1[i][0] && SI == N1[i][1]){

cout << EI[k] << ' ' << SI << endl;

N1[i][0] = -1;

AgentIsNear = true;

T = true;

break;

}

if(T) break;

}

if(!AgentIsNear){

for(int i = 0; i < L; i++){

bool T = false; //Для прерывания цикла

for(int k = 0; k < E; k++){

if(N1[i][0] == EI[k]){

cout << EI[k] << ' ' << N1[i][1] << endl;

N1[i][0] = -1;

T = true;

break;

}

if(T) break;

}

Идея решения: Всё предельно просто: Если агент находится вблизи одного из шлюзов, закрываем переход между агентом и этим шлюзом. Иначе закрываем переход между шлюзом и ближайшим узлом.

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame