#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int par[N];
int find(int x) { return par[x] = par[x] == x ? x : find(par[x]); }
int main() {
while (true) {
for (int i = 1; i <= (int)1e5; ++i) par[i] = i;
vector<pair<int, int>> ex;
while (true) {
int n, m;
if (cin >> n) {
if (n != -1)
cin >> m;
else
break;
ex.push_back({n, m});
} else
return 0;
}
int cnt = 0;
for (auto &it : ex) {
auto u = it.first, v = it.second;
u = find(u);
v = find(v);
if (u == v)
cnt++;
else
par[u] = v;
}
cout << cnt << endl;
}
}
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1010;
int a[N], b[N];
int par[25010];
int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
struct ed {
int u, v;
ll w;
bool operator<(const ed &b) const { return w < b.w; }
};
ll dist(int i, int j) {
ll dx = a[i] - a[j];
ll dy = b[i] - b[j];
return dx * dx + dy * dy;
}
vector<ed> E;
int n;
int main() {
for (int i = 0; i <= 25000; ++i) par[i] = i;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
E.push_back({i, j, dist(i, j)});
}
}
sort(E.begin(), E.end());
int sel = 0;
for (auto [u, v, w] : E) {
u = find(u);
v = find(v);
if (u == v) continue;
par[u] = v;
sel++;
if (sel == n - 1) {
cout << w << endl;
return 0;
}
}
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int N = 2e5 + 10;
vector<int> adj[N];
vector<int> close;
int par[N];
bool ans[N];
bool check[N];
int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) par[i] = i;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 0; i < n; ++i) {
int c;
cin >> c;
close.push_back(c);
}
// 倒序遍历close，逐个“打开”
int cc = 0; // Connected Composnets
for (int i = n - 1; i >= 0; --i) {
cc++;
int u = close[i];
check[u] = true;
for (auto v : adj[u]) {
if (check[v]) {
int fu = find(u), fv = find(v);
if (fu != fv) {
cc--;
par[fu] = fv;
}
}
}
if (cc == 1) ans[i] = true;
}
for (int i = 0; i < n; ++i) {
cout << (ans[i] ? "YES\n" : "NO\n");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 100020;
int n, m;
int par[N];
int arr[N]; // 这题不是最小生成树，而是将需要交换的奶牛都连起来
struct edge {
int a, b, w;
bool operator<(const edge& x) const { return w > x.w; }
} h[N];
int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) par[i] = i;
for (int i = 1; i <= n; ++i) cin >> arr[i];
for (int i = 1; i <= m; ++i) cin >> h[i].a >> h[i].b >> h[i].w;
int ans = -1, cnt = 0;
sort(h + 1, h + m + 1);
for (int i = 1; i <= m; ++i) {
// 判断是否连通
while (find(cnt) == find(arr[cnt])) {
cnt++;
if (cnt >= n) {
goto End;
}
}
auto [a, b, w] = h[i];
int fa = find(a), fb = find(b);
if (fa != fb) {
par[fa] = fb;
ans = w;
}
}
End:
cout << ans << endl;
return 0;
}
// 嗯，体力活没错了
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int g[N * N];
int par[N * N];
int siz[N * N];
struct edge {
int u, v, w;
bool operator<(const edge &x) const { return w < x.w; }
};
vector<edge> e;
void add(int i, int j, int ti, int tj) {
int u = n * i + j;
int v = n * ti + tj;
int fall = abs(g[u] - g[v]);
e.push_back({u, v, fall});
}
int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }
int main() {
cin >> n;
for (int i = 0; i <= n * n; ++i) {
par[i] = i;
siz[i] = 1;
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) cin >> g[n * i + j];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int ti = i + 1, tj = j;
if (ti < n) add(i, j, ti, tj);
ti--, tj++;
if (tj < n) add(i, j, ti, tj);
}
}
sort(e.begin(), e.end());
int sel = 0, ans = -1;
for (int i = 0; i < e.size(); ++i) {
auto [u, v, w] = e[i];
int fu = find(u), fv = find(v);
if (fu == fv) continue;
par[fu] = fv;
siz[fv] += siz[fu];
if (siz[fv] >= (n * n + 1) / 2) {
ans = w;
break;
}
}
cout << ans << endl;
}
#include<bits/stdc++.h>
using namespace std;
long long dx[3]={0, 1, 0}, dy[3]={0, 0, 1};
long long n, m, t;
long long cnt, tot;
long long ans;
struct node{
long long x, y, dis;
}a[250005];
long long f[505][505];
long long father[250005],size[250005];
long long num[505][505],v[250005];
long long find(long long x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
bool cmp(node x,node y)
{
return x.dis<y.dis;
}
int main()
{
for(int i=1;i<=250004;i++)
size[i]=1,father[i]=i;
scanf("%lld%lld%lld",&n,&m,&t);
tot=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
scanf("%lld",&f[i][j]);
tot+=1;
num[i][j]=tot;
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
int flag;
scanf("%d",&flag);
if(flag) v[num[i][j]]=1;
for (int k=1;k<=2;k++)
{
int tx=i+dx[k],ty=j+dy[k];
if (tx<n+1&&ty<m+1) a[++cnt]=(node){num[i][j],num[tx][ty],abs(f[i][j]-f[tx][ty])};
}
}
}//建图
sort(a+1,a+1+cnt,cmp);//排序
for(int i=1;i<=cnt;i++)//不断加边
{
int x=a[i].x,y=a[i].y;
int fx=find(x), fy=find(y);
if(fx==fy)continue;
if (size[fx]+size[fy]>=t)
{
if (size[fx]<t)ans+=a[i].dis*v[fx];
if (size[fy]<t)ans+=a[i].dis*v[fy];
}
if (size[fx]>size[fy]) swap(fx,fy);
father[fx]=fy;
size[fy]+=size[fx],v[fy]+=v[fx];
}
printf("%lld",ans);//输出答案
return 0;
}