P3469-[POI2008]BLO-Blockade

- 日理万妓 2023-06-01 08:57 2阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define pb push_back
     6 #define maxn (500000+39)
     7 
     8 typedef long long ll;
     9 using namespace std;
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 int N,M;
    26 int tot = 1;
    27 int num = 0;
    28 int head[maxn],ver[maxn*2],Next[maxn*2];
    29 int dfn[maxn],low[maxn],Size[maxn];
    30 ll ans[maxn];
    31 bool cut[maxn];
    32 void add(int x,int y)
    33 {
    34     ver[++tot] = y;
    35     Next[tot] = head[x];
    36     head[x] = tot;
    37 }
    38 void tarjan(int x)
    39 {
    40     dfn[x] = low[x] = ++num;
    41     Size[x] = 1;
    42     int flag = 0,sum = 0;
    43     for(int i = head[x]; i; i = Next[i])
    44     {
    45         int y = ver[i];
    46         if(!dfn[y])
    47         {
    48             tarjan(y);
    49             Size[x] += Size[y];
    50             low[x] = min(low[x],low[y]);
    51             if(low[y] >= dfn[x])
    52             {
    53                 flag ++;
    54                 ans[x] += (ll)Size[y]*(N-Size[y]);
    55                 sum += Size[y];
    56                 if(x != 1 || flag > 1)
    57                     cut[x] = true;
    58             }
    59         }
    60         else
    61             low[x] = min(low[x],dfn[y]);
    62     }
    63     if(cut[x])
    64         ans[x] += (ll)(N-sum-1)*(sum+1)+(N-1);
    65     else
    66         ans[x] = 2*(N-1);
    67 }
    68 int main()
    69 {
    70     N = read(),M = read();
    71     _for(i,1,M+1)
    72     {
    73         int x = read();
    74         int y = read();
    75         if(x==y)
    76             continue;
    77         add(x,y);
    78         add(y,x);
    79     }
    80     tarjan(1);
    81     _for(i,1,N+1)
    82     write(ans[i]),putchar('\n');
    83     return 0;
    84 }

转载于:https://www.cnblogs.com/Asurudo/p/11605969.html