CodingTrip-携程プログラミング大会-第一題-石ハサミ布
4361 ワード
はさみ石布
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1246 Accepted Submission(s): 375
Problem Description
Input
Output
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1246 Accepted Submission(s): 375
Problem Description
M ， 1－M ， ， ， 。 （ ， ， ， ）
M ：
："1 A B"， A B 。
："2 A B"， A B 。
M ， ， N ， 、 。
， ， 。
1） ；
2） A B M ；
3） A A。
M N， 。
（1 <= M <= 10,000），（0 <= N <= 10,000）
Input
1 K， K 。
， 1 M、N， 。
2 N+1 ， X，A，B， ，X（1 2） 。
Output
， ， 。
Sample Input
3
43 11
1 4 3
2 3 3
1 4 1
1 4 4
2 3 3
1 2 2
2 1 4
1 1 1
2 1 4
2 3 4
2 3 2
66 9
2 3 1
2 4 4
2 1 2
2 4 3
2 4 2
2 2 3
1 3 2
1 2 1
1 1 1
6 7
2 3 7
2 1 2
2 4 4
1 2 1
1 3 2
1 2 3
2 1 3
Sample Output
5
4
3
。。 ， 。。
#include<cstdio>
const int maxn = 50000+10;
int p[maxn]; //
int r[maxn];// 0 ，1 ，2
void set(int n) //
{
for(int x = 1; x <= n; x++)
{
p[x] = x; //
r[x] = 0;// ，
}
}
int find(int x) //
{
if(x == p[x]) return x;
int t = p[x];
p[x] = find(p[x]);
r[x] = (r[x]+r[t])%3; //
return p[x];
}
void Union(int x, int y, int d)
{
int fx = find(x);
int fy = find(y);
p[fy] = fx; // ： x ， x
r[fy] = (r[x]-r[y]+3+(d-1))%3; //
}
int main()
{
int n, m,k;
scanf("%d",&k);
while(k--)
{
scanf("%d%d", &n, &m);
set(n);
int ans = 0;
int d, x, y;
while(m--)
{
scanf("%d%d%d", &d, &x, &y);
if(x > n || y > n || (d == 2 && x == y)) ans++; // ， ，
else if(find(x) == find(y)) // ， ，
{
if(d == 1 && r[x] != r[y]) ans++; // x y
if(d == 2 && (r[x]+1)%3 != r[y]) ans++; // x y ( Uinon(x, y) ， WA ！！！)
}
else Union(x, y, d); // ，
}
printf("%d
", ans);
}
return 0;
}