无向图输出奇点 使用C语言
时间: 2024-02-21 21:29:31 浏览: 16
一个无向图中的奇点指的是,如果删除该点后,图会被分成多个不连通的部分,那么这个点就是奇点。下面是一个简单的 C 语言代码实现,可以输出无向图中的所有奇点:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXV 1000
int V, E; // 顶点数和边数
int head[MAXV]; // 邻接表头
int nxt[MAXV * MAXV]; // 邻接表next指针
int cnt; // 邻接表计数器
int dfn[MAXV], low[MAXV]; // dfn数组和low数组
int vis[MAXV]; // 标记数组
int idx; // 时间戳
bool ans[MAXV]; // 记录答案
// 添加一条边
void add_edge(int u, int v) {
nxt[++cnt] = head[u];
head[u] = cnt;
nxt[cnt] = v;
}
// 求min函数
int min(int a, int b) {
return a < b ? a : b;
}
// 深度优先搜索函数
void dfs(int u, int fa) {
vis[u] = 1;
dfn[u] = low[u] = ++idx;
int child = 0;
for (int i = head[u]; i; i = nxt[i]) {
int v = nxt[i];
if (v == fa) continue;
if (!vis[v]) {
child++;
dfs(v, u);
low[u] = min(low[u], low[v]);
if ((fa == -1 && child > 1) || (fa != -1 && dfn[u] <= low[v])) ans[u] = true;
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
scanf("%d%d", &V, &E);
for (int i = 1; i <= E; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
for (int i = 1; i <= V; i++) {
if (!vis[i]) dfs(i, -1);
}
for (int i = 1; i <= V; i++) {
if (ans[i]) printf("%d ", i);
}
return 0;
}
```
这个算法的时间复杂度是 $O(V+E)$,其中 $V$ 是顶点数,$E$ 是边数。