- #include "iostream"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#define ll long long#define bug(x) cout << x << " " << "UUUUU" << endl;#define mem(a) memset(a, 0, sizeof(a))#define mp(x, y) make_pair(x, y)#define pb(x) push_back(x) using namespace std;
- const long long INF = 1e18 + 1LL;
- const int inf = 1e9 + 1e8;
- const int N = 1e5 + 100;
- const ll mod = 1e9 + 7;
- int pre[N << 1],
- n,
- m;
- void init(int n) {
- for (int i = 0; i <= 3 * n; ++i) pre[i] = i;
- }
- int finds(int x) {
- return pre[x] = pre[x] == x ? x: finds(pre[x]);
- }
- void unions(int x, int y) {
- int fx = finds(x),
- fy = finds(y);
- pre[fy] = fx;
- }
- int main() {
- //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
- cin >> n >> m;
- init(n);
- int t = 0;
- for (int i = 1; i <= m; ++i) {
- int t,
- x,
- y;
- scanf("%d%d%d", &t, &x, &y);
- if (x > n || y > n || x < 1 || y < 1 || (t == 2 && x == y)) {
- printf("%d ", i);
- continue;
- }
- if (t == 1) {
- if (finds(x) == finds(y + n) || finds(x) == finds(y + 2 * n)) {
- printf("%d ", i);
- } else {
- unions(x, y);
- unions(x + n, y + n);
- unions(x + 2 * n, y + 2 * n);
- }
- } else {
- if (finds(x) == finds(y) || finds(x) == finds(y + 2 * n)) {
- printf("%d ", i);
- } else {
- unions(x, y + n);
- unions(x + n, y + 2 * n);
- unions(x + 2 * n, y);
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2226088.html