💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
最初の行は、テスト例の数を示します.各テストケースの最初の行には、100000を超えない友人関係の数Fが与えられる.次のF行は友達関係を作る順番に与えられます.友人関係は2人のユーザのIDからなり,アルファベットの大文字または小文字の長さが20未満の文字列のみである.
🧺しゅつりょく
友達関係があるたびに、二人の友達ネットワークに何人いるかを知るプログラムを作成します.

🔋サンプルI/O

🔮入力例

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

🔮サンプル出力

2
3
4
2
2
4

💉もんだいぶんせき

🔋ぶんかつ

分離セット

🔋難易度

金貨II

💉問題を解く

🔋解法

この問題はハッシュと分離セットを混合した問題である.
解決策は簡単だ.
入力した友達の中で、既知の友達でなければ、数字は彼の名前で現れます.
この数字は毎回1が増え、既知の友人であればそのまま続けます.
どうせ今度[]演算子でそのキーに対応する値を探せばいい
すべての情報を更新した場合は、この2つの情報を統合します.
その後、結果値は、配列に入力されたaまたはbの親ノードの2番目のインデックスとなり、その配列の各メンバーには独自の数があります.

🔋ソースコード

#include <bits/stdc++.h>

constexpr int MAX = 1000000;

int parent[MAX], fcount[MAX];

int getParent(int value) {
	if (parent[value] == value) return value;
	return parent[value] = getParent(parent[value]);
}

void Union(int a, int b) {
	int xa = getParent(a);
	int xb = getParent(b);
	if (xa < xb) {
		parent[xb] = xa;
		fcount[xa] += fcount[xb];
	}
	else if (xb < xa) {
		parent[xa] = xb;
		fcount[xb] += fcount[xa];
	}
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	int T, M;

	std::cin >> T;
	for (int k = 0; k < T; ++k) {
		int count = 0;
		std::map<std::string, int> m;

		std::cin >> M;

		for (int i = 0; i < MAX; ++i) {
			parent[i] = i;
			fcount[i] = 1;
		}

		for (int j = 0; j < M; ++j) {
			int sa, sb;
			std::string a, b;
			std::cin >> a >> b;
			auto it1 = m.find(a);
            
            		//만약 알려지지않은 친구라면
			if (it1 == m.end()) m[a] = count++;

			auto it2 = m.find(b);
            
            		//만약 알려지지않은 친구라면
			if (it2 == m.end()) m[b] = count++;

			Union(m[a], m[b]);

			std::cout << fcount[getParent(m[a])] << '\n';
		}
	}
}

最近試合の準備のために、私の好きな最大流量やbfsの問題を解決しています.
私は解けなかった分離セットの問題を解いています.
分離セット問題の解は,グラフィック問題に比べて相対的に少ない.
今回は区間と問題と一緒にいろいろな問題をやります.

💉終了時..。

以前もお話ししましたが
プログラミング自体は1年前に始まったのですが、
白俊問題が本格的に始まったのは2~3週間前
以前、私はネットやウィンドウプログラミングなどで5番を挿入し、アルゴリズムに移動しました.

本格的にアルゴリズムの問題を解くようになって間もなくですが、
今度の試合は予選でも合格します.がんばってください.
(もう少し解けば黄金!!!がんばれ~~~!!!
ちょっとTMIでしたが、昨夜徹夜した後、とても眠い気持ちで、朝にコロナ注射を打って帰ってきて、3~4時間も寝て、アルゴリズムを勉強しました...
気になる部分があればコメントで質問しましょう~