526互联

AtCoder Beginner Contest 287 - C (图论简单题)

发布时间 2023-08-22 20:56:16作者: Qiansui

目录

C - Path Graph?

题意
判断给定的无向简单图是不是一条链

思路
n 个顶点 m 条边的无向图若为一条链，那么边数 \(m = n - 1\)，n 个顶点相互可达，任意一个顶点的度不超过 2

利用并查集判整体连通性，在建图时统计度数，最后判断即可

由此，n 个顶点，n - 1 条边的无向连通图，每个顶点的度不超过 2，是一条链

代码

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;

struct DSU{
	int num;
	vector<int> fa;
	DSU(int x = maxm) : num(x), fa(x + 1){
		for(int i = 0; i <= x; ++ i) fa[i] = i;
	}
	int findfa(int x){//迭代实现，用于数范围大时
		while (x != fa[x]) x = fa[x] = fa[fa[x]];
		return x;
	}
	// int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }//递归实现，压缩路径
	void merge(int u, int v){
		fa[findfa(u)] = findfa(v); return ;
	}
	bool same(int u, int v){ return findfa(u) == findfa(v); }
};

void solve(){
	int n, m;
	cin >> n >> m;
	DSU dsu(n);
	vector<int> d(n + 1, 0);
	bool f = false;
	for(int i = 0; i < m; ++ i){
		int u, v;
		cin >> u >> v;
		dsu.merge(u, v);
		++ d[u]; ++ d[v];
		if(d[u] > 2 || d[v] > 2) f = true;
	}
	for(int i = 2; i <= n; ++ i){
		if(!dsu.same(1, i)){
			f = true; break;
		}
	}
	if(m != n - 1 || f) cout << "No\n";
	else cout << "Yes\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}