新朋友
2025-01-22 18:59:54
发布于：上海
25阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
vector<int>field[200009];
vector<bool>vis(200009);
int n , m;
long long ans , sum;
void dfs(int x)
{
vis[x] = true;
ans++;
for(auto y : field[x])
{
if(!vis[y])
dfs(y);
}
}
int main()
{
cin >> n >> m; //n个结点 m条边
for(int i = 0; i < m; i++)
{
int x , y;
cin >> x >> y;
field[x].push_back(y) , field[y].push_back(x);
}
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
ans = 0;
dfs(i);
sum += ans * (ans - 1) / 2;
}
}
cout << sum- m;
return 0;
}
这里空空如也
有帮助，赞一个