@codeforces - 141E@ Clearing Up

@description@
@solution@
@accepted code@
@details@

@description@

给定一个 N 个点 M 条边的图，每条为黑色或者白色。

现在让你求一个生成树，使得生成树中黑色边数量等于白色边数量。

Input

第一行两个整数 n, m (1 ≤ n ≤ 10^3, 1 ≤ m ≤ 10^5)。

接下来 m 行，每行描述了一条边 x, y，并给定它的颜色 —— S 为白色，M 为黑色。

注意可以有重边自环。

Output

如果无解，输出 -1。

否则，先输出边的数量，再在下一行依次给出每条边的编号（根据输入顺序）。

如果有多解，输出任意一个解。

Examples

Input

3 3

1 2 S

1 3 M

2 3 S

Output

2

2 1

@solution@

考虑黑色边中有一些必要边：即使加入所有的白边，也需要这些必要边才能保证连通。

白色边，类似地也有必要边的定义：加入所有的黑边也需要这些边才能连通。

可以通过并查集 + 先扫描白色边 + 再尝试加入黑色边求出黑色必要边。同理可以求出白色必要边。

不妨考虑一种情况：即所有边都不是必要边。

这种情况下，黑色边可以让整张图保持连通，白色边也可以让整张图保持连通。

那么我只需要任意加入 (n - 1) / 2 条不形成环的白边，一定可以另外选出 (n - 1) / 2 条黑边形成生成树。

至于为什么。将白边连接的连通块缩成一个新点，则新图中黑边依然可以让整张图保持连通，而连通图一定可以求出一个生成树。

实现直接并查集加 (n - 1) / 2 条白边，再尽量多地塞黑边。

假如我把必要边连接的连通块缩成点，此时所有边都不为必要边，则归于上面那一种情况。

注意特殊情况，如 n - 1 为奇数，或整张图根本不连通，或必要边太多等。

@accepted code@

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = 100000;

int x[MAXN + 5], y[MAXN + 5];

vector<int>v[2], ans;

bool tag[2][MAXN + 5];

int fa[MAXN + 5], n, m;

int find(int x) {

	return fa[x] = (fa[x] == x ? x : find(fa[x]));

}

bool unite(int x, int y) {

	int fx = find(x), fy = find(y);

	if( fx != fy ) {

		fa[fx] = fy;

		return true;

	}

	else return false;

}

int tot[2];

void get(int t) {

	for(int i=1;i<=n;i++) fa[i] = i;

	for(int i=0;i<v[!t].size();i++)

		unite(x[v[!t][i]], y[v[!t][i]]);

	for(int i=0;i<v[t].size();i++)

		if( unite(x[v[t][i]], y[v[t][i]]) )

			ans.push_back(v[t][i]), tot[t]++, tag[t][i] = true;

}

int main() {

	scanf("%d%d", &n, &m);

	for(int i=1;i<=m;i++) {

		scanf("%d%d", &x[i], &y[i]);

		char ch = getchar();

		while( ch != 'S' && ch != 'M' )

			ch = getchar();

		if( ch == 'S' ) v[0].push_back(i);

		if( ch == 'M' ) v[1].push_back(i);

	}

	if( (n - 1) & 1 ) {

		puts("-1");

		return 0;

	}

	int mid = (n - 1) >> 1;

	get(0), get(1);

	if( tot[0] > mid || tot[1] > mid ) {

		puts("-1");

		return 0;

	}

	for(int i=1;i<=n;i++) fa[i] = i;

	for(int i=0;i<ans.size();i++) unite(x[ans[i]], y[ans[i]]);

	for(int i=0;i<v[0].size()&&tot[0]<mid;i++)

		if( !tag[0][i] && unite(x[v[0][i]], y[v[0][i]]) )

			ans.push_back(v[0][i]), tot[0]++, tag[0][i] = true;

	for(int i=0;i<v[1].size()&&tot[1]<mid;i++)

		if( !tag[1][i] && unite(x[v[1][i]], y[v[1][i]]) )

			ans.push_back(v[1][i]), tot[1]++, tag[1][i] = true;

	if( tot[0] != mid || tot[1] != mid ) {

		puts("-1");

		return 0;

	}

	printf("%d\n", ans.size());

	for(int i=0;i<ans.size();i++)

		printf("%d ", ans[i]);

}

@details@

定睛一看。嗯？wqs二分？

不对wqs二分只能求最小权和不能求方案。

注意各种无解的情况吧。其他没有什么细节。

如果一句话总结的话，大概就是：任意一个连通块必然有生成树。

巴特西

@codeforces - 141E@ Clearing Up

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章