#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
set <int> in[maxn], out[maxn];
set <pair <int, int>> incoming[maxn], outgoing[maxn];
queue <pair <int, int>> Q;
int par[maxn];
int sub[maxn];
int root(int x) {
if(par[x] == x) return x;
return par[x] = root(par[x]);
}
bool change(set <int> &t, set <int> &r, int i, int j) {
t.erase(i); t.insert(j);
return r.count(j);
}
void join(int x, int y) {
x = root(x);
y = root(y);
if(incoming[x].size() + outgoing[x].size() > incoming[y].size() + outgoing[y].size()) swap(x, y);
if(x != y) {
par[x] = y;
sub[y] += sub[x];
for(int i : in[x]) {
in[y].insert(i);
if(change(out[i], in[i], x, y)) Q.emplace(i, y);
}
for(int i : out[x]) {
out[y].insert(i);
if(change(in[i], out[i], x, y)) Q.emplace(i, y);
}
for(auto i : incoming[x]) {
if(root(i.second) == root(y)) {
outgoing[y].erase(make_pair(i.second, i.first));
continue;
}
incoming[y].insert(i);
}
for(auto i : outgoing[x]) {
if(root(i.second) == root(y)) {
incoming[y].erase(make_pair(i.second, i.first));
continue;
}
outgoing[y].insert(i);
}
}
}
bool exists(int i, int j) {
i = root(i); j = root(j);
return out[i].count(j);
}
int sz(int i) {
set <int> s;
for(auto j : incoming[i]) s.insert(j.second);
return s.size();
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
par[i] = i;
sub[i] = 1;
}
vector <pair <int, int>> edge;
for(int x = 1; x <= m; x++) {
int p, q;
scanf("%d %d", &p, &q);
incoming[root(q)].insert(make_pair(q, p));
outgoing[root(p)].insert(make_pair(p, q));
p = root(p);
q = root(q);
out[p].insert(q);
in[q].insert(p);
if(exists(p, q) && exists(q, p)) Q.emplace(root(p), root(q));
while(!Q.empty()) {
int p = Q.front().first;
int q = Q.front().second;
Q.pop();
join(p, q);
}
long long ans = 0;
for(int i = 1; i <= n; i++) {
if(root(i) == i) {
ans += 1LL * sub[i] * (sub[i] - 1);
ans += 1LL * sub[i] * sz(i);
}
}
printf("%lld\n", ans);
}
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p, &q);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
