-
Notifications
You must be signed in to change notification settings - Fork 1
/
JourneyToTheMoon.cpp
executable file
·62 lines (48 loc) · 1.25 KB
/
JourneyToTheMoon.cpp
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
55
56
57
58
59
60
61
62
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define FOR( i, a, b ) for( int i = a ; i < b ; i++ )
#define PII pair< int, int >
void make( vector< PII > & in, int size ){
FOR( i, 0, size ){
in[ i ].first = i;
in[ i ].second = 1;
}
}
int find( vector< PII > & in , int toFind ){
if( in[ toFind ].first == toFind ) return toFind;
else return in[ toFind ].first = find( in, in[ toFind ].first );
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n;
int m;
int a;
int b;
long long result = 0;
cin >> n >> m ;
vector< PII > in( n );
vector< int > help ( n, 0 );
make( in, n );
FOR( i, 0, m ){
cin >> a >> b;
int fa = find( in, a );
int fb = find( in, b );
if( fa != fb ){
in[ fa ].second += in[ fb ].second;
in[ fb ].first = fa;
}
}
FOR( i, 0, n ){
int fa = find( in, i );
if( help[ fa ] == 0 ){
result += in[ fa ].second * ( n - in[ fa ].second );
help[ fa ] = 1;
}
}
cout << result/2 << endl;
return 0;
}