Problem Statement
对于无向图 G=(V,E)，我们将有且只有一个环的、大于 2 个顶点的无向连通图称之为章鱼图，因为其形状像是一个环（身体）带着若干个树（触手），故得名。
给定一个无向图，请你判断是不是只有一个章鱼子图存在。
输入第一行是一个正整数 T (1≤T≤5)，表示数据的组数。
每组数据的第一行是两个正整数 N,M (1≤N,M≤105)，表示给定的无向图有 N 个点，M 条边。
接下来的 M 行，每行给出一条边两个端点的顶点编号。注意：顶点编号从 1 开始，并且题目保证任何边不会重复给出，且没有自环。
Output
对于每组数据，如果给定的图里只有一个章鱼子图，则在一行中输出 Yes 和章鱼子图环的大小（及环中顶点数），其间以 1 个空格分隔。
否则，则在一行中输出 No 和图中章鱼子图的个数，其间以 1 个空格分隔。
Solving
要确定给定无向图中有且仅有一个章鱼子图，则需确定整张图中有且仅有一个各项顶点入度均为2的环，如果有环内节点的入度大于2，则代表其构成的是类似于蜂窝结构的特异环，其并非章鱼环，所以解决此题我们仅需要使用拓扑排序排除图中的枝干（不参与构成任何环的节点），再用DFS遍历的方式去除所有特异环，其留下的所有入度为2的节点所构成的环一定就是可以构成章鱼子图的环，此时我们仅需要判断子图数量是否只有一个，判断过程中使用DFS去除已经标记过的环，过程中进行环内节点计数，最后按照章鱼环数输出要求的数据即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
struct node
{
int to,next;
};
void solve()
{
int n,m;
cin >> n >> m;
vector<int> head(n+1,0);
vector<node> edge(2*m+5);
vector<int> deg(n+1,0);// 入度
int cnt = 0;
int ans = 0;
int anscnt = 0;
auto add = [&](int u,int v) -> void
{
edge[++cnt] = {v,head[u]};
head[u] = cnt;
};
for(int i=1;i<=m;i++)
{
int u,v;
cin >> u >> v;
add(u,v);
add(v,u);
deg[v]++,deg[u]++;
}
// 拓扑排序去除枝干
auto toposort = [&]() -> void
{
queue<int> q;
for(int i=1;i<=n;i++) if(deg[i] == 1) q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
deg[u]--;
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(deg[v] > 1)
{
deg[v]--;
if(deg[v]==1) q.push(v);
}
}
}
};
toposort();
// 此时图中不参与构成环状结构的节点的入度都清为0
// for(int i=1;i<=n;i++) cerr << deg[i] << ' ';
// DFS遍历找环的数量
auto dfs = [&](auto &&self,int u) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(deg[v])
{
anscnt++; //不断更新环内节点数量
deg[v] = 0;
self(self,v);
}
}
};
// 清除所有特异环
for(int i=1;i<=n;i++)
{
if(deg[i] and deg[i] != 2)
{
dfs(dfs,i);
}
}
// 获得章鱼子图的数量
for(int i=1;i<=n;i++)
{
if(deg[i] == 2)
{
ans++;
anscnt = 0;
dfs(dfs,i);
}
}
if(ans == 1)
{
cout << "Yes " << anscnt << endl;
return;
}
else
{
cout << "No " << ans << endl;
}
}
|