acmicpc.net 1717(Disjoint-set), 11866,1158(조세퍼스 문제.)

https://www.acmicpc.net/problem/1717

기본 문제. cin,cout쓰면 시간초과가 걸리므로 printf, scanf를 쓰자.

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

// 트리를 이용해 상호 배제적 집합을 구현한다.
struct OptimizedDisjointSet {
	vector<int> parent, rank;

	OptimizedDisjointSet(int n) : parent(n), rank(n, 1) {
		for(int i = 0; i < n; i++)
			parent[i] = i;
	}

	// u 가 속한 트리의 루트의 번호를 반환한다
	int find(int u) {
		if(u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}

	// u 가 속한 트리와 v 가 속한 트리를 합친다
	void merge(int u, int v) {
		u = find(u); v = find(v);
		// 이미 둘이 같은 트리에 속한 경우
		if(u == v) return;
		if(rank[u] > rank[v]) swap(u, v);
		// 이제 항상 rank[v] 가 더 크므로 u 를 v 의 자식으로 넣는다
		if(rank[u] == rank[v]) rank[v]++;
		parent[u] = v;
	}
};
int main() 
{
	ios::sync_with_stdio(false); 
	int n,m;
	scanf("%d %d",&n,&m);//cin>>n>>m;
	OptimizedDisjointSet d(n+1);
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);//cin>>a>>b>>c;
		if(a==0)
			d.merge(b,c);
		else
		{
			if(d.find(b)==d.find(c))
				printf("YES\n");//cout<<"YES\n";
			else
				printf("NO\n");//cout<<"NO\n";
		}

	}
	return 0;
}

https://www.acmicpc.net/problem/11866

https://www.acmicpc.net/problem/1158

가장 기초적인 조세퍼스 문제.

#include<list>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

void josephus(int n, int k) {
	queue<int> survivors;
	for(int i = 1; i <= n; i++) survivors.push(i);

	while(survivors.size()) {
		for(int i = 0; i < k-1; i++) {
			survivors.push(survivors.front());
			survivors.pop();
		}

		cout<<survivors.front();
		survivors.pop();
		if(survivors.size())
			cout<<", ";
	}
}

int main() 
{
    int n, k;
    cin >> n >> k;
	cout<<"<";
    josephus(n, k);
	cout<<">\n";
}

k값이 클 경우 아래 소스가 더 효과적이다. 시간복잡도가 O(n*k)에서 O(n*n)으로 변한다.

#include<list>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

void josephus(int n, int k) {
	list<int> survivors;
	for(int i = 1; i <= n; i++) survivors.push_back(i);

	list<int>::iterator kill = survivors.begin();
	while(n) {
		for(int i = 0; i < (k-1) % n; i++) {
			++kill;
			if(kill == survivors.end()) kill = survivors.begin();
		}

		cout<<*kill;
		kill = survivors.erase(kill);
		
		if(kill == survivors.end()) kill = survivors.begin();
		--n;
		if(n)
			cout<<", ";
	}
}

int main() 
{
    int n, k;
    cin >> n >> k;
	cout<<"<";
    josephus(n, k);
	cout<<">\n";
}

dp로도 짤수있고 시간복잡도가 최대 O(n)이었나 그정도로 짧아질수 있다고 하는데 그건 알게되면 추가.