题意分析

本题描述了一个电话电缆网络，由若干地点通过双向线路连接，每个地点有电话交换站。当某个地点发生电力故障导致交换站停止运行时，可能使该地点不可达，甚至影响其他原本可互通地点的通信。要求找出网络中所有关键地点（即发生故障会影响其他通信能力的地点）的数目。

解题思路

1. 数据结构与初始化：
   • 使用邻接表G[maxn]存储图的连接关系，pre[maxn]记录每个节点在深度优先搜索（DFS）过程中首次被访问的时间戳，low[maxn]记录每个节点及其子树中能够回溯到的最早的祖先节点的时间戳，iscut[maxn]标记每个节点是否为关键地点，dfs_clock用于记录时间戳。
   • init函数用于初始化这些数组和时间戳，将pre数组和iscut数组清零，dfs_clock设为0。
2. 深度优先搜索（DFS）：
   • dfs函数实现深度优先搜索，参数u为当前节点，fa为u的父节点。
   • 首先初始化lowu和pre[u]为当前时间戳++dfs_clock，并记录子节点数量child。
   • 遍历当前节点u的所有邻接节点v：
     • 如果v未被访问（pre[v] == 0），则递归调用dfs(v, u)，更新lowu为lowu和lowv中的较小值，并根据条件判断u是否为关键地点（对于根节点u == 1，若子节点数child > 1则为关键地点；对于非根节点u != 1，若pre[u] <= low[v]则为关键地点）。
     • 如果v已被访问且v不是u的父节点（pre[v] < pre[u] && v != fa），则更新lowu为lowu和pre[v]中的较小值。
   • 最后返回low[u] = lowu。
3. 主函数处理：
   • 在main函数中，通过循环读取输入，每次读取一个网络的描述。
   • 对于每个网络，先清空邻接表，然后读取网络连接信息，将每条边加入邻接表。
   • 调用init函数初始化，再从节点1开始进行深度优先搜索dfs(1, -1)。
   • 统计iscut数组中标记为关键地点的节点数量cnt，并输出。

复杂度分析

1. 时间复杂度：
   • 对于每个网络，读取输入的时间复杂度为$O(e)$，其中$e$是边的数量（因为每条边至少会在某一行出现）。
   • 深度优先搜索的时间复杂度为$O(n + e)$，其中$n$是节点数量。在最坏情况下，$e$最大为$n(n - 1) / 2$（完全图），所以整体时间复杂度为$O(n^2)$。
2. 空间复杂度：
   • 邻接表G[maxn]存储图的连接关系，空间复杂度为$O(e)$，其中$e$是边的数量。
   • 其他数组pre[maxn]、low[maxn]、iscut[maxn]的空间复杂度为$O(n)$。
   • 因此，总的空间复杂度为$O(n + e)$，在最坏情况下为$O(n^2)$。

代码实现

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 100 + 10;
int pre[maxn], low[maxn], N, dfs_clock;
bool iscut[maxn];
vector<int> G[maxn];

// 初始化函数
void init()
{
    dfs_clock = 0;
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
}

// 深度优先搜索函数
int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock, child = 0;
    int cnt = G[u].size();
    for(int i = 0; i < cnt; i++)
    {
        int v = G[u][i];
        if(!pre[v])
        {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if((u == 1 && child > 1) || (u != 1 && pre[u] <= low[v])) iscut[u] = 1;
        }
        else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]);
    }
    return low[u] = lowu;
}

int main()
{
    int u, v, i;
    while(scanf("%d", &N) == 1 && N)
    {
        for(i = 1; i <= N; i++) G[i].clear();
        while(scanf("%d", &u) == 1 && u)
        {
            while(getchar() != '\n')
            {
                scanf("%d", &v);
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }
        init();
        dfs(1, -1);
        int cnt = 0;
        for(i = 1; i <= N; i++) if(iscut[i]) cnt++;
        printf("%d\n", cnt);
    }
    return 0;
}

🧠 题解（Solution）

✅ 问题本质

本题是一个无向图割点（Articulation Point）问题。

在一个无向连通图中，如果去掉某个顶点及其相关边，会导致图变得不连通，那么这个顶点就是一个割点，也称为关键点或关节点。

🔍 解题思路

建图：根据输入构建无向图；

Tarjan算法或DFS时间戳法查找割点：

使用 DFS 遍历图，记录每个节点的访问时间（dfn）和能够回溯到的最早祖先（low）；

若满足条件：

对于根节点：若有两个及以上的子树；

对于非根节点：若存在子节点 $v$，使得 $low[v] \geq dfn[u]$，则 $u$ 是割点；

统计割点个数。

📌 算法复杂度

构建图：$O(N + M)$；

DFS 查找割点：$O(N + M)$；

对每个测试块独立处理。

🧮 简要示例说明

第一个网络（编号 5）：

5

5 1 2 3 4

图结构是：只有 5 与其他所有点相连，形成一个星形图，5 是唯一的中心节点，若断开它，其它节点无法互通 ⇒ 答案为 $1$。

第二个网络：

6

2 1 3

5 4 6 2

对应图中，2 和 5 是连接多个区域的关键点，断开任意一个都会让图不连通 ⇒ 答案为 $2$。

代码实现：

#include<cstring>
#include<cstdio>
using namespace std;
#define N 20005

int n,m,p,dfs_clock,ans;
int tot,point[N],nxt[N*2],v[N*2];
int dfn[N],low[N],is_cut[N];
bool flag;

void clear()
{
    dfs_clock=ans=0;
    tot=0;memset(v,0,sizeof(v));memset(point,0,sizeof(point));memset(nxt,0,sizeof(nxt));
    memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(is_cut,0,sizeof(is_cut));
}
int read()
{
    int x=0; char ch=getchar();
    while (ch<'0'||ch>'9')
    {
        ch=getchar();
        if (ch=='\n') flag=true;
    }
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
        if (ch=='\n') flag=true;
    }
    return x;
}
void add(int x,int y)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++dfs_clock;
    for (int i=point[x];i;i=nxt[i])
        if (!dfn[v[i]])
        {
            tarjan(v[i]);
            low[x]=min(low[x],low[v[i]]);
            if (dfn[x]<=low[v[i]]) is_cut[x]++;
        }
    else low[x]=min(low[x],dfn[v[i]]);
}
int main()
{
    while (1)
    {
        n=read();
        if (!n) break;
        clear();
        while (1)
        {
            m=read();
            if (!m) break;flag=false;
            while (!flag)
            {
                p=read();
                add(m,p);
            }
        }
        for (int i=1;i<=n;++i)
            if (!dfn[i]) tarjan(i);
        for (int i=1;i<=n;++i)
            if ((i==1&&is_cut[i]>1)||(i!=1&&is_cut[i])) ans++;
        printf("%d\n",ans);
    }
}