#6 #10 WA 求助
查看原帖
#6 #10 WA 求助
347089
STA_Morlin楼主2022/12/25 12:55
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int man = 1e5+10, mam = 5e5+10;
int read () {
    int x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) x = (x<<1)+(x<<3)+(c^48), c = getchar();
    return x*f;	
}
class Graph {
public:
    int hed[man], len = 1;
    int nxt[mam<<1], to[mam<<1];
    void Ins (int u, int v) {
        to[++len] = v;
        nxt[len] = hed[u];
        hed[u] = len;
        return ;
    }
} G;

int n = read(), m = read(), cnt;
ll dfn[man], low[man], fa[man], siz[man], res[man], cut[man];
void tarjan (int x, int cur) {
	int son = 0, sum = 0;
    dfn[x] = low[x] = ++ cnt;
    siz[x] = 1, res[x] = 0;
    for (int i = G.hed[x]; i; i = G.nxt[i]) {
        int t = G.to[i];
        if (!dfn[t]) {
            tarjan(t, i); // to son
            siz[x] += siz[t]; // update size
            low[x] = min(low[x], low[t]); // unless father, count low
            if (low[t] >= dfn[x]) { // can't go to fa unless go fa
        		res[x] += siz[t]*(n-siz[t]);
        		// printf("A%d %d %d\n", x, t, siz[t]);
            	sum += siz[t]; // plus x can't go's point
            	if (x!=1 || ++son>1) // have two sontree
            		cut[x] = 1;
        	}
        } else low[x] = min(low[x], dfn[t]);
    } res[x] = cut[x]?res[x]+(n-1)+(n-sum-1)*(sum+1):(n-1)<<1; // count cuttree
    // printf("KKK %d %d\n", x, cut[x]);
    return ;
}
int main () {
    for (int u, v, i = 1; i <= m; ++ i) u = read(), v = read(), G.Ins(u, v), G.Ins(v, u);
    tarjan(1, -1);
    for (int i = 1; i <= n; ++ i) printf("%lld\n", res[i]);
    return 0;
}
2022/12/25 12:55
加载中...