#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 = 1e5 + 5;
int n, m, pSet[N], sz[N];
vector<int> graph[N];
int findSet(int u) {
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];
void dfs(int u) {
vis[u] = 1;
vec.pb(u);
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(!vis[v])
dfs(v);
}
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
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(!vis[findSet(i)] && sz[findSet(i)] >= 2) {
vec.clear();
dfs(findSet(i));
for(int j = 0; j < vec.size() - 1; j++)
unionSet(vec[j], vec[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];
memset(vis, 0, sizeof(vis));
long long total = 0;
for(int i = 1; i <= n; i++) {
//cout << findSet(i) << "\n";
if(!vis[findSet(i)]) {
//cout << sz[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(int)':
friends.cpp:53:22: 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:72:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < graph[i].size() - 1; j++)
~~^~~~~~~~~~~~~~~~~~~~~
friends.cpp:77:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < graph[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
friends.cpp:91:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < vec.size() - 1; j++)
~~^~~~~~~~~~~~~~~~
friends.cpp:96:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < graph[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5160 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
5240 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
6392 KB |
Output is correct |
| 2 |
Incorrect |
122 ms |
9464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
