#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 2010;
int n, par[maxn], m;
int find_leader(int v)
{
if (par[v] == v)
return v;
return (par[v] = find_leader(par[v]));
}
int sz[maxn];
set < int > in_adj[maxn], out_adj[maxn];
ll calc(int v)
{
ll s = sz[v];
return s * (s - 1 + (ll)(in_adj[v].size()));
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
par[i] = i;
sz[i] = 1;
}
ll edges = 0;
for (int i = 1; i <= m; i ++)
{
int v, u;
cin >> v >> u;
edges = edges - calc(find_leader(v));
edges = edges - calc(find_leader(u));
int lv = find_leader(v), lu = find_leader(u);
if (in_adj[lv].find(lu) != in_adj[lv].end())
{
in_adj[lv].erase(lu);
for (int u : in_adj[lu])
in_adj[lv].insert(u);
sz[lv] += sz[lu];
par[lu] = lv;
edges = edges + calc(lv);
}
else
{
in_adj[lu].insert(v);
edges = edges + calc(find_leader(lv));
edges = edges + calc(find_leader(lu));
}
cout << edges << endl;
//for (int j = 1; j <= n; j ++)
//cout << "sz " << j << " " << sz[j] << endl;
}
}
int main()
{
solve();
return 0;
}
/**
6 7
1 2
2 3
3 4
4 5
5 6
6 5
5 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |