Решение задачи "Катание на Коньках" с Codeforces

Без пояснения   Просмотров: 15


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

Мы предполагаем, что Байтек может сооружать сугробы только в точках с целочисленными координатами.

Код

#include <bits/stdc++.h>
using namespace std;
long long n, xy[1000][1000];
bool b[1000]={0};
void dsu(long long i)
{
	b[i]=1;
	for(long long j=1;j<=n;j++)
	{
		if(!b[j] & (xy[0][i]==xy[0][j] | xy[1][i]==xy[1][j]))
		dsu(j);
	}
}

int main()
{
	cin>>n;
	for(long long i=1;i<=n;i++)
		cin>>xy[0][i]>>xy[1][i];		
	long long ans=-1;
	for(long long i=1;i<=n;i++)
	{
		if(!b[i])
		{
			dsu(i);
			ans++;
		}
	}
	cout<<ans;
}

         


<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор Photo" /> Автор:


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться