HDU 4496 并查集逆向思维

给你n个点m条边，保证已经是个连通图，问每次按顺序去掉给定的一条边，当前的连通块数量。

与其正过来思考当前这边会不会是桥，不如倒过来在n个点即n个连通块下建图，检查其连通性，就能知道个数了

/** @Date    : 2017-09-21 23:26:20

  * @FileName: HDU 4496 并查集 逆向思维.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int n, m;

PII p[N];

int ans[N];//

int fa[10010];

int find(int x)

{

	if(x != fa[x])

		fa[x] = find(fa[x]);

	return fa[x];

}

int join(int a, int b)

{

	int x = find(a);

	int y = find(b);

	if(x != y)

	{

		fa[y] = x;

		return 1;

	}

	return 0;

}

int main()

{

	while(~scanf("%d%d", &n, &m))

	{

		for(int i = 0; i <= n; i++)

			fa[i] = i;

		MMF(ans);

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

		{

			int u, v;

			scanf("%d%d", &u, &v);

			p[i] = MP(u, v);

		}

		int cnt = n;

		for(int i = m; i >= 1; i--)

		{

			ans[i] = cnt;

			if(join(p[i].fi, p[i].se))

				cnt--;

		}

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

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

	}

    return 0;

}

巴特西

HDU 4496 并查集逆向思维

最新文章

热门文章

巴特西

HDU 4496 并查集 逆向思维

最新文章

热门文章

HDU 4496 并查集逆向思维