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

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


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

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

Код

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

         

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



Комментарии

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