题目

题解

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
#define ll long long
#define pii pair<int, int>
#define ld long double
const int maxn = 2e5 + 5, inf = 1e9, maxm = 4e4 + 5, base = 337;
const int N = 2e5;
// const int mod = 1e9 + 7;
const int mod = 998244353;
// const __int128 mod = 212370440130137957LL;
int n, m;
int a[maxn];void solve(){ll res = 0;int k, q;cin >> n >> m;// for(int i = 1; i <= n; i++){//     cin >> a[i];// }vector<vector<pii>> G(n + 1);set<pii> S;for(int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;if(u > v) swap(u, v);if(find(G[u].begin(), G[u].end(), pii{v, (w ^ 1)}) != G[u].end()){S.insert({u, v});}G[u].pb({v, w});G[v].pb({u, w});}res = n + S.size();int cnt = 0;for(auto [u, v] : S){if(G[u].size() < 3 || G[v].size() < 3) continue;pii p, p2;for(auto [w, c] : G[u]){if(w == v) continue;p = {w, c};}for(auto [w, c] : G[v]){if(w == u) continue;p2 = {w, c};if(w == p.first && c != p.second){res++;}}}auto check = [&](int u) -> bool {int cnt[2] = {0};for(auto [v, w] : G[u]){cnt[w]++;}return cnt[0] == 2 && cnt[1] == 1;};auto have = [&](int u, int v) -> bool {return find(G[u].begin(), G[u].end(), pii{v, 1}) != G[u].end();};for(int u = 1; u <= n; u++){if(G[u].size() < 3) continue;if(!check(u)) continue;// vector<int> vec;int v = 0, x = 0, y = 0;for(auto [z, w] : G[u]){if(w == 0){if(check(z)) v = z;else x = z;}}if(!v || !x) continue;for(auto [z, w] : G[v]){if(w == 0 && z != u && z != x){y = z;if(have(x, y) && (have(x, u) && have(y, v) || have(x, v) && have(y, u))){cnt++;}}}}res += cnt / 2;cout << res << '\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout << fixed << setprecision(9);int T = 1;// set<pii> S;// cin >> T;while (T--){solve();}return 0;
}