#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct dsu{
int n;
vector<int> sz, p;
dsu(int nn){
n = nn;
sz.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] != x) p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b){
a = get(a), b = get(b);
if(a == b) return;
if(sz[b] > sz[a]) swap(a, b);
sz[a]+=sz[b];
sz[b] = 0;
p[b] = a;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
map<pair<int, int>, int> mp;
dsu ds(n);
vector<vector<int>> v(n);
for(int i = 0; i < m; i++){
int a, b; cin >> a >> b; a--, b--;
int x = min(a, b), y = max(a, b);
mp[{x, y}]++;
if(mp[{x, y}] == 2){
ds.unite(x, y);
}
v[a].pb(b);
ll ans = 0;
for(int j = 0; j < n; j++){
set<int> s;
s.insert(ds.get(j));
for(int x: v[j]) s.insert(ds.get(x));
for(int x: s) ans+=ds.sz[x];
ans--;
}
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
