对于两端都>k的边 先全部取了
对剩下的边能取就取
用并查集维护
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <cstring> #include <cstdio> #include <cstdlib> #include <ctime> #include <cmath> #include <vector> #include <queue> #include <deque> #include <map> #include <set> #include <stack> #include <iostream> #include <algorithm> #include <string> #include <functional> #include <sstream> using namespace std; typedef long long ll; typedef long double ld; const int maxn = 1000005; struct line { int fr, to; }li[maxn * 2]; int fa[maxn], n, m, k; int getfa(int now) { return (!fa[now]) ? now : fa[now] = getfa(fa[now]); } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; ++i) { scanf("%d%d", &li[i].fr, &li[i].to); if (li[i].fr > k && li[i].to > k) if (getfa(li[i].fr) != getfa(li[i].to)) fa[getfa(li[i].fr)] = getfa(li[i].to); } int ans = 0; for (int i = 0; i < m; ++i) if (li[i].fr <= k || li[i].to <= k) { if (getfa(li[i].fr) != getfa(li[i].to)) fa[getfa(li[i].fr)] = getfa(li[i].to); else ++ans; } printf("%d", ans); } |