2020ICPC·小米 網路選拔賽第一場 D題 Router Mesh【Tarjan求割點和子樹】

傳送門：Router Mesh

題意

給你一個無向圖，你需要求出每次洗掉 i i i點(i=1,2,…,n)后，有多少個連通分量，

思路

• 每次 d f s dfs dfs能搜出一個連通分量，并求出每個點 u u u在深度優先搜索生成樹中往下有 c h i l d [ u ] child[u] child[u]個子樹分支，在 d f s dfs dfs程序中，只有當!dfn[u]&&low[v]>=dfn[u]才有child[u]++（詳見代碼），因為這樣 c h i l d [ u ] child[u] child[u]統計的才是 u u u點子樹的數量，
• 如果洗掉的點 u u u是根節點，顯然它是割點，刪掉之后新增連通分量數為 c h i l d [ u ] child[u] child[u]，
• 否則，刪掉之后新增連通分量數為 c h i l d [ u ] + 1 child[u]+1 child[u]+1，因為它的上方還有一個連通分量，

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m;
vector<int>g[N];
bool fa[N];
int dfn[N],low[N];
int tim=0;
int child[N]; // 每個點的子樹個數
void dfs(int u)
{
    dfn[u]=low[u]=++tim;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            	child[u]++;
        }
        else // 回退邊
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void solve()
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            cnt++; // 初始時所有連通塊個數
            fa[i]=1; // i是這個連通塊的祖先節點
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i])
        {
            child[i]=cnt-1+child[i];
        }
        else
        {
            child[i]=cnt-1+child[i]+1;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    solve();
    for(int i=1;i<=n;i++)
        i==n?printf("%d\n",child[i]):printf("%d ",child[i]);
    return 0;
}
/*
5 1
1 2
ans:4 4 3 3 3

6 5
1 2
2 3
3 1
4 5
5 6
ans:2 2 2 2 3 2
*/

還有就是被牛客的編譯環境搞了一波心態：如果把dfs函式回傳值寫成int，然后又沒return，洛谷的在線IDE和本地codeblocks沒一點問題，提交到牛客就會給你錯誤（段錯誤或者超時），