#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int N, M;
int par[100010], size[100010];
vector<int> E[100010];
int Find(int a) {
if (par[a] == a) return a;
return par[a] = Find(par[a]);
}
void Union(int a, int b) {
if (Find(a) == Find(b)) return;
size[Find(a)] += size[Find(b)];
par[Find(b)] = Find(a);
}
void dfs(int key, int cur) {
Union(key, cur);
for (int nxt : E[cur]) {
if (Find(nxt) == Find(cur)) continue;
dfs(key, nxt);
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> M;
for (int i=0; i<M; i++) {
int x, y; cin >> x >> y;
E[x].push_back(y);
}
for (int i=1; i<=N; i++) par[i] = i, size[i] = 1;
for (int i=1; i<=N; i++) {
if (E[i].size() >= 2) {
for (int j=1; j<E[i].size(); j++) {
Union(E[i][0], E[i][j]);
dfs(E[i][0], E[i][0]);
dfs(E[i][j], E[i][j]);
}
}
}
ll ans = 0;
for (int i=1; i<=N; i++) {
if (Find(i) != i) continue;
ans += (ll)size[i] * (size[i]-1);
}
for (int i=1; i<=N; i++) {
for (int edge : E[i]) {
if (Find(i) != Find(edge)) ++ans;
}
}
cout << ans;
}
Compilation message
friends.cpp: In function 'int main()':
friends.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=1; j<E[i].size(); j++) {
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2724 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 18 |
Correct |
4 ms |
2680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2780 KB |
Output is correct |
| 3 |
Correct |
12 ms |
3260 KB |
Output is correct |
| 4 |
Correct |
98 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
70 ms |
4836 KB |
Output is correct |
| 6 |
Correct |
160 ms |
6364 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
9 ms |
2936 KB |
Output is correct |
| 9 |
Correct |
25 ms |
3192 KB |
Output is correct |
| 10 |
Correct |
27 ms |
3832 KB |
Output is correct |
| 11 |
Correct |
161 ms |
6264 KB |
Output is correct |
| 12 |
Correct |
10 ms |
3192 KB |
Output is correct |
| 13 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 14 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 15 |
Correct |
9 ms |
2940 KB |
Output is correct |
| 16 |
Correct |
19 ms |
3448 KB |
Output is correct |
| 17 |
Correct |
157 ms |
6264 KB |
Output is correct |
| 18 |
Correct |
5 ms |
2936 KB |
Output is correct |
| 19 |
Correct |
6 ms |
3064 KB |
Output is correct |
| 20 |
Correct |
161 ms |
6264 KB |
Output is correct |
| 21 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 22 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 23 |
Correct |
8 ms |
3192 KB |
Output is correct |
| 24 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 25 |
Correct |
5 ms |
2936 KB |
Output is correct |
| 26 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 27 |
Correct |
5 ms |
2936 KB |
Output is correct |
| 28 |
Correct |
6 ms |
2936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
296 ms |
5624 KB |
Output is correct |
| 2 |
Correct |
144 ms |
9932 KB |
Output is correct |
| 3 |
Correct |
138 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
65 ms |
6596 KB |
Output is correct |
| 5 |
Correct |
30 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
152 ms |
8612 KB |
Output is correct |
| 7 |
Correct |
94 ms |
8572 KB |
Output is correct |
| 8 |
Correct |
88 ms |
8656 KB |
Output is correct |
| 9 |
Correct |
56 ms |
6776 KB |
Output is correct |
| 10 |
Correct |
77 ms |
7800 KB |
Output is correct |
| 11 |
Correct |
131 ms |
9836 KB |
Output is correct |
| 12 |
Correct |
154 ms |
10748 KB |
Output is correct |
| 13 |
Correct |
40 ms |
7672 KB |
Output is correct |
| 14 |
Correct |
123 ms |
6648 KB |
Output is correct |
| 15 |
Correct |
26 ms |
5240 KB |
Output is correct |
| 16 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 17 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 18 |
Correct |
121 ms |
8952 KB |
Output is correct |
| 19 |
Correct |
142 ms |
8828 KB |
Output is correct |
| 20 |
Correct |
65 ms |
6264 KB |
Output is correct |
| 21 |
Correct |
28 ms |
5048 KB |
Output is correct |
| 22 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 23 |
Correct |
61 ms |
4472 KB |
Output is correct |
| 24 |
Correct |
69 ms |
6520 KB |
Output is correct |
| 25 |
Correct |
49 ms |
7672 KB |
Output is correct |
| 26 |
Correct |
79 ms |
10232 KB |
Output is correct |
| 27 |
Correct |
112 ms |
11384 KB |
Output is correct |
| 28 |
Correct |
48 ms |
7288 KB |
Output is correct |
| 29 |
Correct |
47 ms |
7388 KB |
Output is correct |
| 30 |
Correct |
130 ms |
9848 KB |
Output is correct |
| 31 |
Correct |
58 ms |
6136 KB |
Output is correct |
| 32 |
Correct |
42 ms |
7780 KB |
Output is correct |
| 33 |
Correct |
40 ms |
7672 KB |
Output is correct |
| 34 |
Correct |
74 ms |
6736 KB |
Output is correct |
| 35 |
Correct |
40 ms |
7672 KB |
Output is correct |
| 36 |
Correct |
48 ms |
9464 KB |
Output is correct |
| 37 |
Correct |
49 ms |
7288 KB |
Output is correct |
