#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 2010;
int n, par[maxn], m;
int sz[maxn];
int find_leader(int v)
{
if (par[v] == v)
return v;
return (par[v] = find_leader(par[v]));
}
set < int > rem;
set < int > in_adj_diff[maxn];
set < int > in_adj[maxn], out_adj[maxn];
ll calc(int v)
{
///cout << "calc " << v << " " << sz[v] << " " << in_adj_diff[v].size() << endl;
// for (int w : in_adj_diff[v])cout << w << " ";
//cout << endl;
ll s = sz[v];
return s * (s - 1 + (ll)(in_adj_diff[v].size()));
}
ll res;
void unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return;
///cout << "unite " << endl;
if (rem.find(v) == rem.end())
{
res = res - calc(v);
rem.insert(v);
}
if (rem.find(u) == rem.end())
{
res = res - calc(u);
rem.insert(u);
}
vector < int > d;par[u] = v;
sz[v] += sz[u];
for (int w : out_adj[u])
{
if (find_leader(w) == v)
continue;
out_adj[v].insert(w);
if (in_adj_diff[v].find(find_leader(w)) != in_adj_diff[v].end())
{
//cout << "PUSH TO D " << w << endl;
d.push_back(w);
}
}
for (int w : in_adj[u])
{
if (find_leader(w) == v)
continue;
///cout << "to " << v << " " << w << endl;
in_adj_diff[v].insert(w);
if (out_adj[v].find(find_leader(w)) != out_adj[v].end())
d.push_back(w);
}
vector < int > sd;
for (int k : in_adj_diff[v])
{
///cout << v << " : " << k << " " << endl;
if (find_leader(k) == v)
sd.push_back(k);
}
for (int k : sd)
in_adj_diff[v].erase(k);
for (int c : d)
unite(v, c);
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
par[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= m; i ++)
{
int v, u;
cin >> v >> u;
int lv = find_leader(v);
int lu = find_leader(u);
if (v == u)
{
cout << res << endl;
continue;
}
if (in_adj_diff[lv].find(lu) != in_adj_diff[lv].end())
{
rem.clear();
unite(lv, lu);
set < int > st;
for (int c : rem)
st.insert(find_leader(c));
for (int c : st)
res += calc(c);
}
else
{
res = res - calc(lv);
res = res - calc(lu);
out_adj[lv].insert(lu);
in_adj[lu].insert(lv);
in_adj_diff[lu].insert(v);
res = res + calc(lv);
res = res + calc(lu);
}
cout << res << endl;
/** cout << "--------------------" << endl;
for (int i = 1; i <= n; i ++)
{
cout << "vertex " << i << endl;
for (int u : in_adj_diff[i])
cout << u << " ";
cout << endl;
}*/
}
}
int main()
{
solve();
return 0;
}
/**
5 5
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3
4 3
1 2
2 3
3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
