#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int mod = 1e9 + 7;
const int inf = 1e9;
int add(int x, int y) {
return (1ll * x + 1ll * y) % mod;
}
int del(int x, int y) {
return ((1ll * x - 1ll * y) % mod + mod) % mod;
}
int mul(int x, int y) {
return (1ll * x * 1ll * y) % mod;
}
const int N = 2e5 + 5;
int n, m, pSet[N], sz[N];
vector<int> graph[N];
int findSet(int u) {
//cout << u << "\n";
if(u == pSet[u]) return u;
else return pSet[u] = findSet(pSet[u]);
}
void unionSet(int u, int v) {
u = findSet(u), v = findSet(v);
if(u == v) return ;
sz[v] += sz[u];
pSet[u] = v;
}
bool vis[N];
vector<int> vec, gr[N];
queue<int> q;
void dfs() {
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(!vis[v]) {
vis[v] = 1;
q.push(v);
}
unionSet(u, v);
}
}
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
// freopen("test.inp", "r", stdin);
cin >> n >> m;
for(int i = 1; i <= n; i++)
pSet[i] = i, sz[i] = 1;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].pb(v);
}
for(int i = 1; i <= n; i++) {
if(graph[i].size() >= 2) {
for(int j = 0; j < graph[i].size() - 1; j++)
unionSet(graph[i][j], graph[i][j + 1]);
}
}
/*for(int i = 1; i <= n; i++) {
for(int j = 0; j < graph[i].size(); j++) {
int v = graph[i][j];
if(findSet(i) != findSet(v))
gr[findSet(i)].pb(findSet(v));
}
}
for(int i = 1; i <= n; i++) {
graph[i] = gr[i];
gr[i].clear();
}*/
for(int i = 1; i <= n; i++) {
if(sz[findSet(i)] >= 2)
q.push(i), vis[i] = 1;
}
dfs();
/*for(int i = 1; i <= n; i++) {
for(int j = 0; j < graph[i].size(); j++) {
int v = graph[i][j];
if(findSet(i) != findSet(v))
gr[findSet(i)].pb(findSet(v));
}
}
for(int i = 1; i <= n; i++)
graph[i] = gr[i];*/
memset(vis, 0, sizeof(vis));
long long total = 0;
for(int i = 1; i <= n; i++) {
if(!vis[findSet(i)]) {
vis[findSet(i)] = 1;
if(sz[findSet(i)] >= 2)
total += 1ll * sz[findSet(i)] * (sz[findSet(i)] - 1);
else
total += graph[findSet(i)].size();
}
}
cout << total;
}
Compilation message
friends.cpp: In function 'void dfs()':
friends.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < graph[u].size(); i++) {
~~^~~~~~~~~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:81:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < graph[i].size() - 1; j++)
~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9976 KB |
Output is correct |
2 |
Correct |
11 ms |
9976 KB |
Output is correct |
3 |
Correct |
11 ms |
9912 KB |
Output is correct |
4 |
Correct |
11 ms |
9976 KB |
Output is correct |
5 |
Correct |
10 ms |
10104 KB |
Output is correct |
6 |
Correct |
11 ms |
9976 KB |
Output is correct |
7 |
Correct |
11 ms |
9976 KB |
Output is correct |
8 |
Correct |
11 ms |
9976 KB |
Output is correct |
9 |
Correct |
11 ms |
9976 KB |
Output is correct |
10 |
Correct |
11 ms |
9976 KB |
Output is correct |
11 |
Correct |
10 ms |
9976 KB |
Output is correct |
12 |
Correct |
11 ms |
9976 KB |
Output is correct |
13 |
Correct |
11 ms |
9976 KB |
Output is correct |
14 |
Correct |
11 ms |
9980 KB |
Output is correct |
15 |
Correct |
10 ms |
9940 KB |
Output is correct |
16 |
Correct |
11 ms |
9976 KB |
Output is correct |
17 |
Correct |
11 ms |
9896 KB |
Output is correct |
18 |
Correct |
11 ms |
9876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
10104 KB |
Output is correct |
2 |
Correct |
12 ms |
9976 KB |
Output is correct |
3 |
Correct |
19 ms |
10332 KB |
Output is correct |
4 |
Correct |
51 ms |
11100 KB |
Output is correct |
5 |
Correct |
43 ms |
10972 KB |
Output is correct |
6 |
Correct |
64 ms |
11512 KB |
Output is correct |
7 |
Correct |
12 ms |
9976 KB |
Output is correct |
8 |
Correct |
14 ms |
10104 KB |
Output is correct |
9 |
Correct |
18 ms |
10296 KB |
Output is correct |
10 |
Correct |
27 ms |
10616 KB |
Output is correct |
11 |
Correct |
64 ms |
11516 KB |
Output is correct |
12 |
Correct |
17 ms |
10232 KB |
Output is correct |
13 |
Correct |
13 ms |
10104 KB |
Output is correct |
14 |
Correct |
12 ms |
10104 KB |
Output is correct |
15 |
Correct |
15 ms |
10232 KB |
Output is correct |
16 |
Correct |
22 ms |
10488 KB |
Output is correct |
17 |
Correct |
63 ms |
11388 KB |
Output is correct |
18 |
Correct |
13 ms |
10232 KB |
Output is correct |
19 |
Correct |
12 ms |
10236 KB |
Output is correct |
20 |
Correct |
64 ms |
11508 KB |
Output is correct |
21 |
Correct |
13 ms |
10104 KB |
Output is correct |
22 |
Correct |
12 ms |
10104 KB |
Output is correct |
23 |
Correct |
15 ms |
10232 KB |
Output is correct |
24 |
Correct |
13 ms |
10104 KB |
Output is correct |
25 |
Correct |
12 ms |
10104 KB |
Output is correct |
26 |
Correct |
13 ms |
10104 KB |
Output is correct |
27 |
Correct |
20 ms |
10232 KB |
Output is correct |
28 |
Correct |
13 ms |
10104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
11128 KB |
Output is correct |
2 |
Correct |
115 ms |
13816 KB |
Output is correct |
3 |
Correct |
118 ms |
14012 KB |
Output is correct |
4 |
Correct |
69 ms |
12920 KB |
Output is correct |
5 |
Correct |
36 ms |
12108 KB |
Output is correct |
6 |
Correct |
95 ms |
12664 KB |
Output is correct |
7 |
Correct |
90 ms |
13944 KB |
Output is correct |
8 |
Correct |
85 ms |
13944 KB |
Output is correct |
9 |
Correct |
58 ms |
13148 KB |
Output is correct |
10 |
Correct |
76 ms |
13560 KB |
Output is correct |
11 |
Correct |
120 ms |
13948 KB |
Output is correct |
12 |
Correct |
115 ms |
14332 KB |
Output is correct |
13 |
Correct |
50 ms |
13968 KB |
Output is correct |
14 |
Correct |
70 ms |
11680 KB |
Output is correct |
15 |
Correct |
35 ms |
12156 KB |
Output is correct |
16 |
Correct |
14 ms |
10872 KB |
Output is correct |
17 |
Correct |
12 ms |
10744 KB |
Output is correct |
18 |
Correct |
123 ms |
13532 KB |
Output is correct |
19 |
Correct |
111 ms |
13624 KB |
Output is correct |
20 |
Correct |
67 ms |
12716 KB |
Output is correct |
21 |
Correct |
34 ms |
12024 KB |
Output is correct |
22 |
Correct |
12 ms |
10744 KB |
Output is correct |
23 |
Correct |
38 ms |
10872 KB |
Output is correct |
24 |
Correct |
73 ms |
12676 KB |
Output is correct |
25 |
Correct |
52 ms |
14072 KB |
Output is correct |
26 |
Correct |
65 ms |
15612 KB |
Output is correct |
27 |
Correct |
120 ms |
14328 KB |
Output is correct |
28 |
Correct |
71 ms |
13436 KB |
Output is correct |
29 |
Correct |
75 ms |
13304 KB |
Output is correct |
30 |
Correct |
123 ms |
14200 KB |
Output is correct |
31 |
Correct |
69 ms |
12764 KB |
Output is correct |
32 |
Correct |
51 ms |
13916 KB |
Output is correct |
33 |
Correct |
48 ms |
13944 KB |
Output is correct |
34 |
Correct |
56 ms |
13176 KB |
Output is correct |
35 |
Correct |
57 ms |
13984 KB |
Output is correct |
36 |
Correct |
55 ms |
15044 KB |
Output is correct |
37 |
Correct |
56 ms |
13304 KB |
Output is correct |