提出 #73543634

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define LL long long
#define PLL pair<LL, LL>
#define PII pair<int, int>
#define PLI pair<LL, int>
#define int LL
using namespace std;
int n, ncnt = 0;
vector<PII> x, y, z;
vector<vector<int> > g;
vector<int> dfn, low, bel;
stack<int> st;
vector<bool> vis;
void tarjan(int u = 1) {
	dfn[u] = low[u] = ++ncnt;
	st.push(u); vis[u] = 1;
//	cout << u << " u\n";
	for (auto v : g[u]) {
//		cout << u << " " << v << " v\n";
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		while (1) {
			int id = st.top(); st.pop();
			bel[id] = u; vis[id] = 0;
			if (id == u) break;
		}
	}
}
inline void solve() {
	cin >> n;
	while (!st.empty()) st.pop();
	x.clear(); y.clear(); z.clear(); ncnt = 0; vis.clear();
	dfn.clear(); low.clear(); bel.clear(); g.clear();
	x.resize(n + 1); y.resize(n + 1); z.resize(n + 1); vis.resize(n + 1);
	dfn.resize(n + 1); low.resize(n + 1); bel.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> x[i].first >> y[i].first >> z[i].first;
		x[i].second = y[i].second = z[i].second = i;
	}
	sort(x.begin() + 1, x.end());
	sort(y.begin() + 1, y.end());
	sort(z.begin() + 1, z.end());
	reverse(x.begin() + 1, x.end());
	reverse(y.begin() + 1, y.end());
	reverse(z.begin() + 1, z.end());
	g.resize(n + 1);
	for (int i = 1; i < n; i++) {
		g[x[i].second].push_back(x[i + 1].second);
		if (x[i].first == x[i + 1].first) g[x[i + 1].second].push_back(x[i].second);
		g[y[i].second].push_back(y[i + 1].second);
		if (y[i].first == y[i + 1].first) g[y[i + 1].second].push_back(y[i].second);
		g[z[i].second].push_back(z[i + 1].second);
		if (z[i].first == z[i + 1].first) g[z[i + 1].second].push_back(z[i].second);
	}
	tarjan(x[1].second);
//	for (int i = 1; i <= n; i++) {
//		cout << bel[i] << " bel\n";
////		if (!dfn[i]) tarjan(i); 
//	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += (bel[i] == bel[1]);
	}
	cout << ans << "\n";
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t--) solve();
	return 0;
}

提出情報

ジャッジ結果