D-Router Mesh（2020ICPC·小米 网络选拔赛第一场）

D-Router Mesh（2020ICPC·小米 网络选拔赛第一场）

题意

给一个无向图，对每一个结点做一个询问，询问为，若删掉该点（及所有与其相关的连边），整个图有几个连通块？

前置知识：强连通

回顾一下相关知识：

dfn[x]： 中， 实际被访问的时间点。
low[x]： 中， 通过无向边，可回溯到的最早的时间点。
割点：无向连通图中，某点及其相连的边去掉后，图不再联通。

例如：

组成一个连通图， 点去掉后，图将不再联通。所以 点就是一个割点。

判断一个点是不是割点：

图片来自https://www.bilibili.com/video/BV1Q7411e7bM?p=2，有兴趣的小伙伴可以去观看视频
解释一下Case2的图二：虽然 和 是联通的，但是深度优先搜索的顺序是 root->A->B，所以 是 的儿子，那么 就只有一个儿子。故不符合条件。

对于不是根节点的点，我们需要找出，从这个点分支出去，有几个不相连的子树。就是删掉这个点之后增加几个连通块。对于根节点，儿子（“儿子”指的是DFS时的儿子）数量就是增加的联通块数量。注意根节点时不只有增加，还会减少一个连通块，下文会解释。

• 当 不是根节点时，考虑与 相连的点 ，如果 无法回溯到 以上的节点，那么当 被删除后， 就与 的父亲所在的连通块断开了。所以 所在分支就贡献了一个连通块。统计 的所有儿子节点，对贡献求和就是删除 节点后增加的连通块的数量。
  有同学可能要问：
  这种情况的话不是多加了答案吗？
  
  和上面解释根节点的Case2一样，在 遍历时， 是 的儿子节点，不是 的儿子节点，所以 只有一个儿子节点，那么对答案的贡献就是1.

• 当 是根节点时，同样计算所有儿子分支的贡献求和。会发现由于 没有父亲节点，所以就不存在“ 就与 的父亲所在的连通块断开了”的情况，只有 形成了一个新的分支。根节点的所有儿子节点（同上，“儿子节点”是指 遍历时的儿子节点）都会对答案有贡献，然后原来的连通块就只剩 ，然后随着 的删除消失。所以删除根节点后增加的连通块数量是对儿子贡献的求和再减一。

那么删除 节点后的连通块的数量就是原来的连通块数量+删去 后增加的联通块数量。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define m_p make_pair
#define p_i pair<int, int>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n"
#define mem(a, b) memset(a, b, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define fil(a, b) fill(a.begin(), a.end(), b);
#define scl(x) scanf("%lld", &x)
#define sc(x) scanf("%d", &x)
#define pf(x) printf("%d\n", x)
#define pfl(x) printf("%lld\n", x)
#define abs(x) ((x) > 0 ? (x) : -(x))
#define PI acos(-1)
#define lowbit(x) (x & (-x))
#define dg if(debug)
#define nl(i, n) (i == n - 1 ? "\n":" ")
using namespace std;
typedef long long LL;
// typedef __int128 LL;
typedef unsigned long long ULL;
const int maxn = 300005;
const int maxm = 1000005;
const int maxp = 30;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-8;
const double e = 2.718281828;
int debug = 0;

inline int read() {
    int x(0), f(1); char ch(getchar());
    while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n, m;
vector<int> G[maxn];
int num[maxn];

int scccnt;         //强连通分量的数量
int sccno[maxn];    //每个点所在的强连通分量的编号，编号从1开始递增
int dfn[maxn];      //深度优先搜索遍历时结点 u 被搜索的次序
int low[maxn];      //u或u的子树能够追溯到的最早的栈中节点的次序号
int tclock;         //用于递增dfn
stack<int> q;
void init() {
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(sccno, 0, sizeof(sccno));
    scccnt = tclock = 0;
}
void tarjin(int u) {
    ++num[u];
    dfn[u] = low[u] = ++tclock;
    q.push(u);
    for(auto &v : G[u]) {
        if (!dfn[v]) {
            tarjin(v);
            low[u] = min(low[u], low[v]);
            num[u] += (dfn[u] <= low[v]);
        }
        else if (!sccno[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scccnt++;
        int v = -1;
        while (v != u) {
            v = q.top();
            q.pop();
            sccno[v] = scccnt;
        }
    }
}

void sol() {
    init();
    _for(i, m) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    _rep(i, 1, n) {
        if(!dfn[i]) {
            tarjin(i);
            --num[i];
        }
    }
    _rep(i, 1, n) {
        printf("%d%s", scccnt - 1 + num[i], i == n ? "\n":" ");
    }
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    debug = 1;
#endif
    time_t beg, end;
    if(debug) beg = clock();

    n = read(), m = read();
    sol();

    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    return 0;
}