and check
concept:
Union lookup is a data structure
Usually two functions
F
i
n
d
(
)
Find( )
Find(),
U
n
i
o
n
(
)
Union( )
Union() and arrays
f
[
]
f[]
f[] constitutes,
f
[
]
f[]
f[] is used to record its own root
function
f
i
n
d
(
x
)
find(x)
find(x) is used to find
x
x
root of x, function
U
n
i
o
n
(
x
,
y
)
Union(x, y)
Union(x,y) is used to merge two sets.
Introducing the example :)
background:
In an era of a hundred schools of thought fighting (ming), there are many schools of thought, such as: Wudang School, Shaolin School, Huashan School...
Because the times were extremely unsafe at that time, people who did not belong to the same clan would fight when they saw each other (bad social behavior)
But there may be some problems, (may hurt teammates by mistake.
The relationship network is shown in the figure
Relationships are so complicated...
At this time, you can use the union query set to store the relationship,
Such as: Master Ma Zhen is the Daoist Chongxu, and the master of Daoist Chongxu is Zhang Sanfeng,
F i n d ( ) Find() Introduction of Find() function
When Ma Zhen met Lu Feiqing,
Ma Zhen asked, "Dare to ask if you can fight me?"
Lu Feiqing asked back: "Dare to ask which sect you belong to? I belong to the Wudang sect."
To prevent accidental injury,
horse really used
F
i
n
d
(
)
Find( )
Find() function to query its own root.
inline int Find(int x) { //find x's home pie
while(f[x] != x) //If x's master is x himself, then he is the jiapai
x = f[x]; //x then looks for his superiors until he finds the pie
return x; //Home sent to drive~~~
}
But Yes... Ma Zhen – > Taoist priest Chongxu – > Zhang Sanfeng – > Wu when sect, there are too many people asking of, and Time is also very slow of···
(Maybe I haven’t asked yet, it’s already finished)
Therefore, a more efficient
F
i
n
d
(
)
Find()
Find() function, named path compression .
inline int Find(int x) { //inline for optimization
if (f[x] == x) return x; //if x's master is x himself
else return f[x] = find(f[x]); //If not, then continue with your own master
}
After path compression, the relationship storage will become the following form:
You can directly find the faction you belong to to avoid accidental injury, which is good.
U n i o n ( ) Union() Introduction of Union() function
Under the troubled times, the relationship between some of the Huashan Sect's disciples has become more and more bad, and conflicts often occur.
Finally, disciple Feng Qingyang couldn't bear it any longer.
use
U
n
i
o
n
(
)
Union()
Union() took refuge in the Wudang faction.
So the relationship:
U n i o n ( ) letter number of mold plate : Template for Union() function: Template for Union() function:
inline void Union(int x, int y) { //inline optimization
int t1 = Find(x), t2 = Find(y); //Find the master of x and the master of y
if (t1 != t2) f[t2] = t1; //y recognizes x as the master, and the two sets are merged into one
return;
}
Regarding the union check set, there is another key place, that is, initialization
void init() {
for (int i = 1; i <= n; i++)
f[i] = i; //Before accepting a teacher, they are all self-taught, and they are their own masters, that is, they are their own roots.
return;
}
The following is the introduction of the template title:
P3367 [Template] and search
Topic description
As the title, now there is a union query set, you need to complete the merge and query operations.
input format
The first line contains two integers
N
N
N，
M
M
M, means shared
N
N
N elements and
M
M
M operations.
next
M
M
M lines, each containing three integers
Z
i
,
X
i
,
Y
i
Z_i,X_i,Y_i
Zi,Xi,Yi.
when
Z
i
=
1
Z_i = 1
When Zi=1, the
X
i
X_i
Xiand
Y
i
Y_i
The collection that Yi is in is merged.
when
Z
i
=
2
Z_i = 2
When Zi=2, the output
X
i
X_i
Xiand
Y
i
Y_i
Yiis in the same set, yes output
Y
Y
Y ; otherwise output
N
N
N.
output format
for each Z i = 2 Z_i = 2 For the operation of Zi=2, there is a line of output, each line contains an uppercase letter, which is Y Y Y or N N N.
Instructions/Tips
for
30
%
30\%
30% of the data,
N
≤
10
，
M
≤
20
N≤10，M≤20
N≤10，M≤20..
for
70
%
70\%
70% of the data,
N
≤
100
，
M
≤
1
0
3
N≤100，M≤10^3
N≤100，M≤103.
for
100
%
100\%
100% data,
1
≤
N
≤
1
0
4
,
1
≤
M
≤
2
×
1
0
5
1≤N≤10^4,1≤M≤2×10^5
1≤N≤104,1≤M≤2×105.
input sample
4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4
Sample output
N Y N Y
Topic analysis: template questions, sets of templates
C
o
d
e
Code
Code
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[100050];
void init() { //initialization
for (int i = 1; i <= n; i++)
f[i] = i;
}
inline int Find(int x) { //find "root"
if (f[x] == x) return x;
else return f[x] = Find(f[x]);
}
inline void Union(int x, int y) { //Merge collections
int t1 = Find(x), t2 = Find(y);
if (t1 != t2) f[t1] = t2;
}
inline void Check(int x, int y) { //Check conditions
int t1 = Find(x), t2 = Find(y);
if (t1 == t2) puts("Y"); //Faster function than printf, and also automatic line wrapping, but can only refer to variables of type char
else puts("N"); //Faster, prettier, stronger! ! !
}
int main() {
scanf("%d%d", &n, &m);
init();
while (m--) {
int z, x, y;
scanf("%d%d%d", &z, &x, &y);
if (z == 1) Union(x, y);
else Check(x, y);
}
return 0; //perfect ending
}
And look up the extended domain of the set:
basic concept:
In some cases, an element contains more than one attribute, and more than one relationship is passed. Therefore, we can split each element into multiple elements, maintain the transitivity of the relationship when merging, and maintain the transitivity through the extended attributes.
Does it sound complicated, but to put it bluntly, it is to expand the original set several times, and then establish a relationship in the new set.
P2024 [NOI2001] Food chain
Topic description:
There are three types of animals in the animal kingdom
A
,
B
,
C
A,B,C
A,B,C, the food chains of these three types of animals form an interesting loop.
A
A
A eat
B
B
B，
B
B
B eat
C
C
C，
C
C
C eat
A
A
A.
There are N animals, numbered 1-N. Every animal is one of A,B,C, but we don't know which one it is.
Some people describe the food chain relationship formed by these N animals in two ways:
●The first statement is 1 X Y, which means
X
X
X and
Y
Y
Y is homogeneous.
●The second argument is 2 X Y, which means
X
X
X eat
Y
Y
Y .
This person uses the above two statements to say K sentences sentence after sentence to N animals. Some of these K sentences are true and some are false.
When a sentence satisfies one of the following three conditions, the sentence is false, otherwise it is true.
Conditions for judging falsehood
●The current words conflict with some of the previous true words, which are false words.
●Currently speaking
X
X
X or
Y
Y
Y ratio
N
N
Large N is a lie.
●Current word indication
X
X
X eat
X
X
X is a lie.
Your task is to output the total number of falsehoods given N and K sentences.
Input format:
Two integers in the first line
N
，
K
N，K
N, K, means that there are
N
N
N animals,
K
K
K sentences.
The second line begins with one sentence per line (according to the requirements of the title, see the example).
Output format:
One line, an integer, representing the total number of falsehoods.
Input sample:
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample output:
3
hint:
1
≤
N
≤
5
∗
1
0
4
1 ≤ N ≤ 5 ∗ 10^4
1≤N≤5∗104，
1
≤
K
≤
1
0
5
1 ≤ K ≤ 10^5
1≤K≤105.
Parse:
This question needs to save three kinds of relationships, namely: the same kind, the prey, and the natural enemy.
So it is possible to extend the union lookup set, from
n
n
n becomes
3
×
n
3 × n
3×n .
①Use
x
x
x means
x
x
the same kind of x.
②Use
x
+
n
x + n
x+n means
x
x
x's prey.
③Use
x
+
2
×
n
x + 2 × n
x+2×n means
x
x
x's natural enemy.
The judgment of the falsehood is as shown in the title, which is the request
So,
when
d
=
1
d=1
When d=1 and the sentence is true,
d
=
1
Time
{
U
n
i
o
n
(
x
,
y
)
(
x
and
y
Yes
same
kind
)
U
n
i
o
n
(
x
+
n
,
y
+
n
)
(
x
of
hunting
thing
and
y
of
hunting
thing
Yes
same
kind
)
U
n
i
o
n
(
x
+
2
∗
n
,
y
+
2
∗
n
)
(
x
of
sky
enemy
and
y
of
sky
enemy
Yes
same
kind
)
d = 1 Time \left\{ \begin{matrix} Union(x, y) (x and y Yes are the same) \ Union(x + n, y + n) (x of hunting thing and y of hunting thing Yes are the same )\ Union(x + 2 * n, y + 2 * n)(The natural enemy of x and the natural enemy of y are the same)\ \end{matrix} \right.
When d=1 ⎩⎨⎧Union(x,y)(x and y are the same) Union(x+n,y+n)(x’s prey and y’s prey are the same) Union(x+2∗n, y+2∗n)(The natural enemy of x and the natural enemy of y are the same kind)
when
d
=
2
d=2
When d=2 and the sentence is true,
d
=
2
Time
{
U
n
i
o
n
(
x
,
y
+
2
∗
n
)
(
x
Yes
y
of
sky
enemy
)
U
n
i
o
n
(
x
+
n
,
y
)
(
x
of
hunting
thing
Yes
y
)
U
n
i
o
n
(
x
+
2
∗
n
,
y
+
n
)
(
x
of
sky
enemy
Yes
y
of
hunting
thing
)
d = 2 \left\{\begin{matrix} Union (x, y + 2 * n) (x is Y's natural enemy) \ \ Union(x + n, y)(x's prey is y)\ Union (x + 2 * n, y + n)(x's natural enemy is y's prey)\ \end{matrix} \right
When d=2 ⎩⎨⎧Union(x,y+2∗n)(x is y’s natural enemy) Union(x+n,y)(x’s prey is y)Union(x+2∗n,y+ n)(The natural enemy of x is the prey of y)
C
o
d
e
:
Code:
Code:
#include <bits/stdc++.h>
using namespace std;
int ans;
int n, k;
int f[150005];
void init() { //Initialization of extension fields
for (int i = 1; i <= 3 * n; i++) {
f[i] = i;
}
}
inline int Find(int x) { //find the root
if (f[x] == x) return x;
else return f[x] = Find(f[x]);
}
inline void Union(int x, int y) { //Merge collections
int t1 = Find(x), t2 = Find(y);
if (t1 != t2) f[t2] = t1;
}
inline bool check1(int x, int y) { //determine whether they are similar
if (Find(x + n) == Find(y) || Find(x + 2 * n) == Find(y))
return true;
else
return false;
}
inline bool check2(int x, int y) { //Determine if it is prey
if (Find(x) == Find(y) || Find(x + 2 * n) == Find(y))
return true;
else
return false;
}
int main() {
scanf("%d%d", &n, &k);
init();
while (k--) {
int d, x, y;
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n) {ans++; continue;}
switch(d) { //I heard it is faster than if
case 1:
if (check1(x, y)) {ans++; continue;}
else {
Union(x, y);
Union(x + n, y + n);
Union(x + 2 * n, y + 2 * n);
}
break;
case 2:
if (check2(x, y)) {ans++; continue;}
else {
Union(x, y + 2 * n);
Union(x + n, y);
Union(x + 2 * n, y + n);
}
}
}
return !printf("%d", ans);//One more line saved
}
end
(This blog will be continuously updated)