AtCoder Beginner Contest 404 C-G（无F）题解
C. Cycle Graph?题意
给你一个 \(N\) 个顶点 \(M\) 条边的简单（无重边、自环）无向图，第 \(i\) 条边连接节点 \(A_i\) 和 \(B_i\)，判断这个图是不是一个环。
思路
首先一个图是环，要满足点数等于边数，即 \(N=M\)；
其次，这个图必须连通，可以通过 \(\text{DFS}\) 或 \(\text{BFS}\) 搜索判断是否连通（从任意一点开始搜，结束后检查是否每个点都已到达过）；
最后，每个点的度数（所连接的顶点数）必须为 \(2\)。
可以证明，只要满足上述三个条件，这个图一定是一个环。
C++ 代码
#includeusing namespace std;const int maxn=200005;int n,m;int deg;vector g;bool used;void dfs(int v){ used=true; for(int x:g){ if(!used){ dfs(x); } }}int main(){ cin>>n>>m; if(n!=m){ cout>v; g.push_back(v); g.push_back(u); } dfs(1); for(int i=1;i
页:
[1]