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;
}
上一篇:vue build打包后css里的图片路径404不正确的问题


下一篇:Vue style与css的var()