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++ 代码

[code]#includeusing namespace std;const int maxn=200005;int n,m;int deg[maxn];vector g[maxn];bool used[maxn];void dfs(int v){        used[v]=true;        for(int x:g[v]){                if(!used[x]){                        dfs(x);                }        }}int main(){        cin>>n>>m;        if(n!=m){                cout>v;                g.push_back(v);                g[v].push_back(u);        }        dfs(1);        for(int i=1;i

分享、互助 让互联网精神温暖你我

东西不错很实用谢谢分享