# 14082: 【原4082】四通八达

### 题目描述

author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4082

## Sample Input

``````6 3
0 4
1 2
2 4
``````

## Sample Output

``````3
``````

## FineArtz's solution

``````/* 四通八达 */
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

class edge{
public:
edge(int xx, int yy) : x(xx), y(yy) {}
int x = 0, y = 0;
};

int parent[1000005];
int v[1000005] = {0};
vector<edge> e;
map<int, set<int>> ee;
int n, m, cnt = 0;
long long ans;

int find(int x){
while (parent[x] != x){
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

int main(){
cin >> n >> m;
for (int i = 1; i <= m; ++i){
int x, y;
cin >> x >>y;
if (x == y) continue;
if (ee.find(x) != ee.end()){
if (ee[x].find(y) != ee[x].end())
continue;
}
++cnt;
e.emplace_back(x, y);
ee[x].insert(y);
ee[y].insert(x);
}
for (int i = 0; i <= n; ++i)
parent[i] = i;
for (auto i : e){
int p = find(i.x);
int q = find(i.y);
if (p != q)
parent[p] = q;
}
for (int i = 0; i <= n; ++i)
parent[i] = find(i);
for (int i = 0; i <= n; ++i)
++v[parent[i]];
for (int i = 0; i <= n; ++i){
if (v[i] != 0){
ans += v[i] * (v[i] - 1) / 2;
}
}
cout << ans - cnt << endl;
return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e6;

struct edgeNode {
int data;
edgeNode *next;

edgeNode(int d = 0, edgeNode *n = 0) : data(d), next(n) {}
};

struct verNode {
int data;
int degree;

verNode(int d = 0, edgeNode *h = 0) : data(d), head(h), degree(0) {}
};

int N, M, ans = 0, city = 0, degree = 0;
verNode *nodes[maxN];
bool isVisited[maxN] = {0};

void DFS(int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> N >> M;

for (int i = 0; i <= N; i++) {
nodes[i] = new verNode(i);
}

for (int i = 0; i < M; i++) {
int temp1, temp2;

cin >> temp1 >> temp2;

nodes[temp1]->degree++;
nodes[temp2]->degree++;
}

for (int i = 0; i <= N; i++) {
if (!isVisited[i]) {
city = degree = 0;
DFS(i);
ans += ((city * (city - 1)) - degree) / 2;
}
}

cout << ans;

return 0;
}

void DFS(int i) {
isVisited[i] = 1;
city++;
degree += nodes[i]->degree;