本文共 3215 字，大约阅读时间需要 10 分钟。

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define INF 0x3F3F3F3F
#define DNF 0x7F
#define DBG printf("Debug: %s\n", __FILE__)
typedef struct {
    int to;
    int next;
    int weight;
} Edge;
void add_edge(int f, int t) {
    edge_cnt++;
    edge[edge_cnt].to = t;
    edge[edge_cnt].next = head[f];
    head[f] = edge_cnt++;
}
// 补图表示
bool graph[1005][1005];
vector< vector
      
        > vcc;
int dfn[1005], low[1005], times = 0, top = 0, type = 0;
int mark[1005], color[1005], ans[1005], ok = 0;
void tarjan(int u) {
    dfn[u] = low[u] = times++;
    stack.push(u);
    for (int v = head[u]; v; v = edge[v].next) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                type++;
                while (!stack.empty() && stack.top() != v) {
                    stack.pop();
                    vcc[type].push_back(stack.top());
                }
                vcc[type].push_back(u);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    stack.pop();
}
void dfs(int u) {
    if (ok) return;
    for (int v = head[u]; v; v = edge[v].next) {
        if (mark[v]) {
            if (color[v] == 0) {
                color[v] = -color[u];
                dfs(v);
            } else {
                if (color[v] == color[u]) {
                    ok = 1;
                    return;
                }
            }
        }
    }
}
void init() {
    graph = {false};
    mem(dfn, 0);
    mem(low, 0);
    mem(stack, 0);
    head = {-1};
    ans = {0};
}
int main() {
    #define LOCAL
    freopen("data.in", "r", stdin);
    freopen("odata.out", "w", stdout);
    while (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0) break;
        init();
        graph = {false};
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u][v] = graph[v][u] = true;
        }
        // 构建补图
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (!graph[i][j]) {
                    add_edge(i, j);
                    add_edge(j, i);
                }
            }
        }
        for (int u = 1; u <= n; u++) {
            if (!dfn[u]) {
                tarjan(u);
            }
        }
        for (int i = 1; i <= type; i++) {
            ok = 0;
            for (auto v : vcc[i]) {
                mark[v] = 1;
            }
            color[vcc[i][0]] = 1;
            dfs(vcc[i][0]);
            if (ok) {
                for (auto v : vcc[i]) {
                    ans[v] = 1;
                }
            }
            for (auto v : vcc[i]) {
                mark[v] = 0;
                color[v] = 0;
            }
        }
        int total = count(ans);
        cout << total << endl;
    }
}
      
     
    
   

上述代码实现了图的双连接分量识别算法，主要包括以下几个部分：

代码中主要使用了以下技术：

• Depth-First Search (DFS)
• Tarjan 算法
• 图的双连通分量识别
• 补图构建

代码的主要功能是对输入图中的顶点进行双连通分量识别，可以应用于网络攻击 анализ、病毒传播分析等场景。