#include <bits/stdc++.h>
#define ll long long
using namespace std;
class UnionFind {
public:
vector<ll> root, rank, group, dependencies;
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;
dependencies[i] = 0;
}
}
ll find(ll a) {
if (root[a] == a) return a;
return root[a] = find(root[a]);
}
void join(ll a, ll b){
ll roota = find(a), rootb = find(b);
if (roota != rootb) {
if (rank[roota] < rank[rootb]) {
root[roota] = rootb;
group[rootb] += group[roota];
dependencies[rootb] += dependencies[roota] - 2;
dependencies[roota] = 0;
} else if (rank[rootb] < rank[roota]) {
root[rootb] = roota;
group[roota] += group[rootb];
dependencies[roota] += dependencies[rootb] - 2;
dependencies[rootb] = 0;
} else {
root[roota] = rootb;
rank[rootb]++;
group[rootb] += group[roota];
dependencies[rootb] += dependencies[roota] - 2;
dependencies[roota] = 0;
}
}
}
bool connected(ll a, ll b) {
return find(a) == find(b);
}
ll getg(ll a) {
return group[find(a)];
}
ll getd(ll a) {
return dependencies[find(a)];
}
void updd(ll a, ll val) {
dependencies[find(a)] += val;
}
};
int main() {
ll n, m, i, a, b, ans = 0, tmp;
queue<ll> todel;
bool found, found2;
cin >> n >> m;
vector<unordered_set<ll>> isfollowing(n + 1), followsof(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];
// check if a and b are part of the same group
found = false;
for (ll neighbor : isfollowing[b]) {
if (uf.connected(neighbor, a)) {
if (found) todel.push(neighbor);
found = true;
}
}
while (not todel.empty()) {
isfollowing[b].erase(todel.front());
todel.pop();
}
// check if a has already been linked to the group that b is in
found2 = false;
for (ll neighbor : followsof[a]) {
if (uf.connected(neighbor, b)) {
if (found2) todel.push(neighbor);
found2 = true;
}
}
while (not todel.empty()) {
followsof[a].erase(todel.front());
todel.pop();
}
// link a to the group that b belongs in if it hasn't been linked before
if (not found and not found2 and not uf.connected(a, b)) {
ans += uf.getg(b);
isfollowing[b].insert(a);
followsof[a].insert(b);
uf.updd(b, 1);
}
found = false;
for (ll neighbor : isfollowing[a]) {
// join the two groups together if there is a mutual connection
if (uf.connected(neighbor, b)) {
if (found) {
todel.push(neighbor);
continue;
}
ans += (uf.getg(a) - 1) * uf.getg(b) + uf.getg(a) * (uf.getg(b) - 1); // mutually connect everyone
ans += uf.getg(a) * (uf.getd(b) - 1) + uf.getg(b) * (uf.getd(a) - 1); // connect dependencies
found = true;
}
}
while (not todel.empty()) {
isfollowing[a].erase(todel.front());
todel.pop();
}
if (found) uf.join(a, b);
cout << ans << endl;
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:67:32: warning: unused variable 'tmp' [-Wunused-variable]
67 | ll n, m, i, a, b, ans = 0, tmp;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
