洛谷題書115【データ構造1-3】集合(そして集合部分を調べます)

73180 ワード
同前 洛谷は単に書きます
記事の目次
  • P 551親戚
  • P 536村村通
  • P 155犯人を拘留する
  • P 892[BOI 2003]グループ
  • P 955[NOI 2015]プログラム自動解析
  • P 4305[JLOI 2011]数字が重複しない
  • P 814ファミリー図
    • P 1551親戚
    テンプレートを検索します
    #include 
#include 
#include 
using namespace std;
const int N = 5e4 + 5;

int fa[N]; //           

void init(int n)
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
     
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
     
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main(void)
{
     
	int n, m, q;
	int x, y;
	
	scanf("%d%d%d", &n, &m, &q);
	init(n);
	for (int i = 0; i < m; i++) {
     
		scanf("%d%d", &x, &y);
		unite(x, y);
	}
	for (int i = 0; i < q; i++) {
     
		scanf("%d%d", &x, &y);
		if (find(x) == find(y)) {
     
			cout << "Yes" << endl;
		} else {
     
			cout << "No" << endl;
		}
	}
	
	return 0;
}
    P 536村村通
    いくつかの連結ブロックがありますか?道路の数は連結ブロックの数を減らします.
    #include 
#include 
#include 
using namespace std;
const int N = 5e4 + 5;

int fa[N]; //           

void init(int n)
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
     
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
     
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main(void)
{
     
	int t, n, m;
	int x, y;

	while (scanf("%d", &n) != EOF && n) {
     
		scanf("%d", &m);
		init(n);
		for (int i = 0; i < m; i++) {
     
			scanf("%d%d", &x, &y);
			unite(x, y);
		}
		int ans = -1;
		for (int i = 1; i <= n; i++)
			if (find(i) == i)
				ans++;
		printf("%d
    "    , ans);
	}
	return 0;
}
    P 155犯人を拘留する
    注意点:犯罪者と敵の敵を統合する
    犯罪者xの最初の敵を一列に記録し、敵があれば、直接にxの敵を一緒にすればいいです.
    最後に二つの敵が一つの部屋にいたと発見したら、その時は終了して答えを出力するしかないです.
    #include 
#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;

int fa[N], foe[N]; //           ，   
int n, m;
struct crim{
     
	int a, b, c;
	bool operator < (const crim &y) const {
     
		return c > y.c;
	}
};
crim arr[N];

void init(int n)
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
     
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
     
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main(void)
{
     
	cin >> n >> m;
	init(n);
	for (int i = 0; i < m; i++) {
     
		scanf("%d%d%d", &arr[i].a, &arr[i].b, &arr[i].c);
	}
	sort(arr, arr + m);
	int res = 0;
	for (int i = 0; i < m; i++) {
     
		//            
		if (find(arr[i].a) == find(arr[i].b)) {
     
			res = arr[i].c;
			break;
		} else {
     
			//      
			if (foe[arr[i].a] == 0) {
     
				foe[arr[i].a] = arr[i].b;
			} else {
     
				unite(foe[arr[i].a], arr[i].b);
			}
			//      
			if (foe[arr[i].b] == 0) {
     
				foe[arr[i].b] = arr[i].a;
			} else {
     
				unite(foe[arr[i].b], arr[i].a);
			}
		}
	}
	cout << res << endl;
	
	return 0;
}
    P 892[BOI 2003]グループ
    一人を敵の敵と合併する
    最後にいくつかの連結ブロックがあると判断すればいいです.
    #include 
#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;

int fa[N], foe[N]; //           ，   
int n, m;

void init(int n)
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
     
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
     
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main(void)
{
     
	char opt;
	int p, q;
	cin >> n >> m;
	init(n);
	while (m--) {
     
		cin >> opt >> p >> q;
		if (opt == 'F') {
     
			unite(p, q);
		} else {
     
			if (foe[p] == 0) {
     
				foe[p] = q;
			} else {
     
				unite(foe[p], q);
			}
			if (foe[q] == 0) {
     
				foe[q] = p;
			} else {
     
				unite(foe[q], p);
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
     
		if (find(i) == i) {
     
			res++;
		}
	}
	cout << res << endl;
	
	return 0;
}
    P 1595[NOI 2015]プログラム自動分析
    心が騒がしい問題です.まず二つの要素を離散化します.e=1なら合併します.そうでなければ記録して、最後に二つの要素が一つの連結ブロック内にあるかどうかを判断します.同じブロック内の数字はきっと同じです.
    #include 
#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 5;

int fa[N]; //           
int xx[N], yy[N];

void init(int n)
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
     
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
     
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main(void)
{
     
	int t, n;
	int a, b, e;
	int idx1, idx2, x, y;
	cin >> t;
	while (t--) {
     
		scanf("%d", &n);
		init(N - 5);
		idx1 = idx2 = 1;
		map<int, int> mp;
		for (int i = 0; i < n; i++) {
     
			scanf("%d%d%d", &a, &b, &e);
			if (mp[a] == 0) {
     
				x = mp[a] = idx1;
				idx1++;
			} else {
     
				x = mp[a];
			}
			if (mp[b] == 0) {
     
				y = mp[b] = idx1;
				idx1++;
			} else {
     
				y = mp[b];
			}
			
			if (e == 1) {
     
				unite(x, y);
			} else {
     
				xx[idx2] = x, yy[idx2] = y;
				idx2++;
			}
		}
		bool flag = 1;
		for (int i = 1; i < idx2; i++) {
     
			//cout << find(xx[i]) << " " << find(yy[i]) << endl;
			if (find(xx[i]) == find(yy[i])) {
     
				flag = 0;
				break;
			}
		}
		cout << (flag ? "YES" : "NO") << endl;
	}
	
	return 0;
}
    P 4305[JLOI 2011]数字は重複しません.
    最初はscanfでタイムアウトしました.クイック読み込みに変更しました.
    #include 
#include 
#include 
#include 
using namespace std;
const int N = 5e4 + 5;

inline int read()
{
     
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){
      if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
} //        C++    

inline void write(int x)
{
     
	if (x < 0) x = ~x + 1, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

int a[N];

int main(void)
{
     
	int t, n;
	int idx, tt;
	t = read();
	while (t--) {
     
		map<int, bool> mp;
		idx = 0;
		n = read();
		while (n--) {
     
			tt = read();
			if (mp[tt] == 0) {
     
				mp[tt] = 1;
				a[idx++] = tt;
			}
		}
		for (int i = 0; i < idx; i++) {
     
			write(a[i]);
			putchar(' ');
		}
		puts("");
	}
	
	return 0;
}
    P 814ファミリースペクトル
    離散化＋検索セットは文字列と下付き文字列を交換し、mapで文字列を下付き文字列に変換し、配列またはmapで下付き文字列に変換する必要があります.
    #include 
#include 
#include 
#include 
using namespace std;
const int N = 5e4 + 5;
typedef long long ll;

int fa[N], foe[N]; //           ，   
int n, m;

void init(int n)
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

int find(int x)
{
     
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

void unite(int x, int y)
{
     
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main(void)
{
     
	int idx = 1;
	char op;
	string s, t;
	string arr[N];
	map<string, int> mp;
	
	init(N - 5);
	while (cin >> op && op != '$') {
     
		if (op == '#') {
     
			cin >> s;
			if (mp[s] == 0) {
     
				mp[s] = idx;
				arr[idx++] = s;
			} 
		} else if (op == '+') {
     
			cin >> t;
			if (mp[t] == 0) {
     
				mp[t] = idx;
				arr[idx++] = t;
			} 
			fa[mp[t]] = mp[s];
		} else {
     
			cin >> s;
			t = arr[find(mp[s])];
			cout << s << " " << t << endl;
		}
		
	}
	
	return 0;
}
    luogu P 1551親戚(そして入門を調べます)