F2. Spanning Tree with One Fixed Degree 并查集+dfs+bfs tarjan+bfs

题目传送门

思路：先不把1及其边加入到集合中去，然后到剩下的边中找连通块，可以用tarjan也可以用并查集。
最后再将1与这些连通块相连接，显然，连通块必须全部和1相连接，如果k小于了连通块数目，那么答案是NO，如果k大于了连通块数目，那么就任意多加几条边就行了（当然不可能是重边）

tarjan+bfs写法：

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
const int N = 2e5 + 5,M=4e5+5;
int e[M], ne[M], h[N], idx;
int dfn[N], low[N], scc_cnt, id[N], scc_size[N], tt;
int stk[N],in_stk[N],top;
vector<int>v;
bool have_id[N];
queue<int>q;
bool st[N];
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++tt;
	stk[++top] = u, in_stk[u] = true;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!dfn[j])
		{
			tarjan(j);
			low[u] = min(low[u], low[j]);
		}
		else if (in_stk[j])
		{
			low[u] = min(low[u], dfn[j]);
		}

	}
	if (dfn[u] == low[u])
	{
		++scc_cnt;
		int temp;
		do{
			temp = stk[top--];
			in_stk[temp] = false;
			id[temp] = scc_cnt;
		} while (temp != u);
	}
}
void bfs(int u)
{
	q.push(u);
	while (!q.empty())
	{
		int k = q.front();
		q.pop();
		for (int i = h[k]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (!st[j])
			{
				cout << k << ' ' << j << endl;
				q.push(j);
				st[j] = 1;
			}

		}
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	memset(h, -1, sizeof h);
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		if (a != 1 && b != 1)
		{
			add(a, b);
			add(b, a);
		}
		else
			v.push_back(max(a, b));
	}
	for (int i = 2; i <= n; i++)
	{
		if(!dfn[i])
		tarjan(i);
	}
	if (scc_cnt > k || v.size() < k)
	{
		cout << "NO\n";
		return 0;
	}
	cout << "YES\n";
	for (int i = 0; i < v.size(); i++)
	{
		int temp = v[i];
		int ff = id[v[i]];
		if (!have_id[ff])
		{
			add(1, temp);
			have_id[ff] = 1;
			k--;
			v[i] = 0;
		}
	}
	if (k)
	{
		for (int i = 0; i < v.size(); i++)
		{
			if (v[i])
			{
				add(1, v[i]);
				k--;
				if (k == 0) break;
			}
		}
	}

	bfs(1);
	return 0;
}

并查集+dfs+bfs写法：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 4e5 + 5;
int e[M], ne[M], h[N], idx;
int pre[N];
vector<int>v;
bool st[N];
queue<int>q;
int find(int x)
{
	return pre[x]==x ? x : pre[x] = find(pre[x]);
}
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
	st[u] = 1;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (st[j]) continue;
		st[j] = 1;
		pre[j] = u;
		dfs(j);
	}
}
void bfs(int u)
{
	q.push(u);
	st[u] = 1;
	while (!q.empty())
	{
		int ff = q.front();
		q.pop();
		for (int i = h[ff]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (!st[j])
			{
				cout << ff << ' ' << j << endl;
				st[j] = 1;
				q.push(j);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= n; i++) pre[i] = i;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		if (a != 1 && b != 1)
		{
			add(a, b);
			add(b, a);
		}
		else
			v.push_back(max(a, b));
	}
	if (v.size() < k)
	{
		cout << "NO\n";
		return 0;
	}
	for (int i = 0; i < v.size(); i++)
	{
		if (pre[i] == i)
		{
			st[i] = 1;
			dfs(v[i]);
		}
	}
	int cnt = 0;
	for (auto& i : v)
	{
		if (pre[i] == i)
		{
			cnt++;
			add(1, i);
		}
		
	}

	if (cnt > k)
	{
		cout << "NO\n";
		return 0;
	}
	cout << "YES\n";
	k -= cnt;
	if (k)
	{
		for (auto& i : v)
		{
			if (pre[i] != i)
			{
				add(1, i);
				k--;
				if (!k)break;
			}
		}
	}
/*	for (int i = h[1]; i != -1; i = ne[i])
	{
		int j = e[i];
		cout << 1 << ' ' << j << endl;
	}
	cout << endl;  */
	memset(st, 0, sizeof st);
	bfs(1);
	return 0;
}