Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using pii = pair<int, int>;
- const int N = 100010;
- int n;
- vector<pii> G[N];
- int U[N], V[N], deg[N], sz[N];
- ll ans[N];
- void dfs(int u, int p, int e)
- {
- sz[u] = 1;
- for (auto v : G[u]) {
- if (v.first != p && deg[v.first] == 0) {
- dfs(v.first, u, v.second);
- sz[u] += sz[v.first];
- }
- }
- ans[e] = (ll)(n-sz[u]) * sz[u];
- }
- int main()
- {
- scanf("%d%*d", &n); // n = m
- for (int i = 1; i <= n; ++i) {
- int u, v;
- scanf("%d%d", &u, &v);
- U[i] = u, V[i] = v;
- G[u].push_back({v, i});
- G[v].push_back({u, i});
- ++deg[u], ++deg[v];
- }
- queue<int> Q;
- for (int u = 1; u <= n; ++u) {
- if (deg[u] == 1)
- Q.push(u);
- }
- while (!Q.empty()) {
- int u = Q.front();
- Q.pop();
- for (auto v : G[u]) {
- if (deg[v.first] > 0) {
- --deg[u];
- if (--deg[v.first] == 1)
- Q.push(v.first);
- }
- }
- }
- for (int u = 1; u <= n; ++u) {
- if (deg[u] == 2) // start from node in cycle only
- dfs(u, 0, 0);
- }
- for (int i = 1; i <= n; ++i) {
- if (i != 1)
- printf(" ");
- if (deg[U[i]] == 2 && deg[V[i]] == 2) // ignore edge in cycle
- ans[i] = 0;
- printf("%lld", ans[i]);
- }
- printf("\n");
- return 0;
- }
Add Comment
Please, Sign In to add comment