题解：AT_abc404_c [ABC404C] Cycle Graph?

· · 题解

题目大意

若一个简单无向图的每个点有两条边且所有点均联通，则输出“Yes”，否则输出“No”。

题目做法

首先记一个将图用vector建好，接着从第一个点开始枚举 n个点，第i个点的下一个点为上一个点的没被访问到的另一个与其连接的点，所以若全都被访问到或与次点相连接的点的数量 \not= 2则输出“No”。当第i个点是最好一个点 (i = n) 时。若跟它相连的两个点都没被访问过，输出“No”。否则输出“Yes”。

代码


#include<bits/stdc++.h>
using namespace std;
int n,m;
bool vis[1000005];
vector<int>vec[200005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v; 
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    int k=1;
    for(int i=1;i<=n;i++){
        if(vec[i].size()!=2){
            cout<<"No";
            return 0;
        }else{
            vis[k]=1;
            if(i!=n){
                if(vis[vec[k][0]]==1&&vis[vec[k][1]]==1){
                    cout<<"No";
                    return 0;
                }else if(vis[vec[k][1]]==1){
                    k=vec[k][0];
                }else{
                    k=vec[k][1];
                }
            }else{
                if(vis[vec[k][0]]!=1&&vis[vec[k][1]]!=1){
                    cout<<"No";
                }
            }

        }
    }
    cout<<"Yes";
    return 0;
}