#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll combs(ll a) {
return (a - 1) * a;
}
class UnionFind {
public:
vector<ll> root, rank, group;
vector<unordered_set<ll>> dependencies;
queue<ll> todel;
UnionFind(ll n) {
root.resize(n);
rank.resize(n);
group.resize(n);
dependencies.resize(n);
for (ll i = 0; i < n; i++) {
root[i] = i;
rank[i] = 1;
group[i] = 1;
}
}
ll find(ll a) {
if (root[a] == a) return a;
return root[a] = find(root[a]);
}
void sUnion(unordered_set<ll>& a, unordered_set<ll>& b, ll roota, ll rootb) {
for (ll elem : b) a.insert(elem);
for (ll elem : a) {
if (find(elem) == roota or find(elem) == rootb) todel.push(elem);
}
while (not todel.empty()) {
a.erase(todel.front());
todel.pop();
}
}
void join(ll a, ll b){
ll roota = find(a), rootb = find(b);
if (rank[roota] < rank[rootb]) {
group[rootb] += group[roota];
sUnion(dependencies[roota], dependencies[rootb], roota, rootb);
root[roota] = rootb;
} else {
group[rootb] += group[roota];
sUnion(dependencies[rootb], dependencies[roota], roota, rootb);
root[roota] = rootb;
if (rank[roota] == rank[rootb]) rank[rootb] ++;
}
}
inline bool connected(ll a, ll b) {
return find(a) == find(b);
}
inline ll getg(ll a) {
return group[find(a)];
}
inline ll getd(ll a) {
return dependencies[find(a)].size();
}
inline void updd(ll a, ll val) {
if (find(val) != find(a)) dependencies[find(a)].insert(val);
}
};
int main() {
ll n, m, i, a, b, ans = 0;
queue<ll> todel;
cin >> n >> m;
vector<unordered_set<ll>> isfollowing(n + 1);
UnionFind uf(n + 1);
vector<vector<ll>> queries(m, vector<ll>(2));
for (i = 0; i < m; i++) cin >> queries[i][0] >> queries[i][1];
for (i = 0; i < m; i++) {
a = queries[i][0];
b = queries[i][1];
if (isfollowing[b].find(a) == isfollowing[b].end()) {
ans -= uf.getd(b) * uf.getg(b);
uf.updd(b, a);
ans += uf.getd(b) * uf.getg(b);
} else if (not uf.connected(a,b)) {
ans -= combs(uf.getg(a));
ans -= combs(uf.getg(b));
ans -= uf.getd(a) * uf.getg(a);
ans -= uf.getd(b) * uf.getg(b);
uf.join(a, b);
ans += combs(uf.getg(a));
ans += uf.getd(a) * uf.getg(a);
}
isfollowing[a].insert(b);
cout << ans << endl;
}
return 0;
}
/*
4 6
1 2
2 3
3 2
2 1
4 1
4 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
