题目描述
自己发现用递归构造的算法可以变成自己想要的样子
比如代码中的递归,明确了结果就是:x==parent[x]的结果.得到的一定是目前的根节点.
还有就是将捕食关系用数字化表达和用距离表示的思维也很稀奇.算法题要多刷!
用距离表示时需要画图理解,设未知量,然后求未知量.
但有些东西y总没有解释清楚,比如后面求d[fa]的式子列的有些牵强
不能根据 (d[a] + x - d[b])%3 == 0 直接得出x = d[b] - d[a],应该配合图形关系得到,否则单看一个式子根本想不出来.
样例
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#define endl '\n'
using namespace std;
using i64 = long long;
const int N = 1e5 + 10;
typedef pair<int, int> pii;
int a[N], b[N];
stack<int> stk1, stk2;
int parent[N], d[N];
int find(int a)
{
if (parent[a] != a)
{
int t = find(parent[a]);//不断递归,补充基础数据,到parent[x] == x时的值时结束
d[a] += d[parent[a]];
parent[a] = t;
}
return parent[a];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) parent[i] = i;
int cnt = 0;
while (k--)
{
int t, a, b; cin >> t >> a >> b;
if (a > n || b > n || (t == 2 && a == b)) cnt++;
else
{
int fa = find(a), fb = find(b);
if (t == 1)
{
if (fa == fb && (d[a] - d[b]) % 3 != 0) cnt++;
else if (fa != fb)
{
parent[fa] = fb;
d[fa] = d[b] - d[a];
}
}
if (t == 2)
{
if (fa == fb && (d[a] + 1 - d[b]) % 3 != 0) cnt++;
else if (fa != fb)
{
parent[fa] = fb;
d[fa] = d[b] - 1 - d[a];
}
}
}
}
cout << cnt << endl;
return 0;
}