题解 | #DongDong认亲戚#

代码1，利用字符串哈希，用map存下来

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
#define ms(a,b) memset((a),(b),sizeof(a))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int mod = 1e9 + 7;

const int P = 131;

const int N = 20010;

const int inf = 0x3f3f3f3f;

const ll lnf = 9e18;

int n, m;
map<ull, ull> p;

ull find( ull x ) {
	if( p[x] != x ) p[x] = find( p[x] );

	return p[x];
}

int main() {
	cin >> n >> m;

	for( int i = 1; i <= n; i++ ) {
		string a;
		cin >> a;
		ull x = 0;

		for( int i = 0; i < a.size(); i++ ) x = x * P + a[i];

		p[x] = x;
	}

	while( m-- ) {
		int op;
		string x, y;
		cin >> op >> x >> y;
		ull c = 0, d = 0;

		for( int i = 0; i < x.size(); i++ ) {
			c = c * P + x[i];
		}

		for( int i = 0; i < y.size(); i++ ) {
			d = d * P + y[i];
		}

		ull fx = find( c ), fy = find( d );

		if( op == 1 ) {
			if( fx != fy ) {
				p[fx] = fy;
			}
		}
		else {
			if( fx == fy ) puts( "1" );
			else puts( "0" );
		}
	}

	return 0;
}

代码2 直接用map存字符串

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
#define ms(a,b) memset((a),(b),sizeof(a))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int mod = 1e9 + 7;

const int P = 131;

const int N = 20010;

const int inf = 0x3f3f3f3f;

const ll lnf = 9e18;

int n, m;
map<string,string> p;

string find( string x ) {
	if( p[x] != x ) p[x] = find( p[x] );

	return p[x];
}

int main() {
	cin >> n >> m;

	for( int i = 1; i <= n; i++ ) {
		string a;
        cin >> a;
		p[a] = a;
	}

	while( m-- ) {
		int op;
		string x, y;
		cin >> op >> x >> y;
		string fx = find( x ), fy = find( y );

		if( op == 1 ) {
			if( fx != fy ) {
				p[fx] = fy;
			}
		}
		else {
			if( fx == fy ) puts( "1" );
			else puts( "0" );
		}
	}

	return 0;
}