洛谷 P1197 [JSOI2008]星球大战 链式前向星 逆向并查集 连通块

链式前向星 逆向并查集 连通块"/>

洛谷 P1197 [JSOI2008]星球大战 链式前向星 逆向并查集 连通块

题目链接：

参考博客：

这个博客超级清晰，建议复习时再反复学习

算法：

1：逆向并查集   2：链式前向星

思路：

1：如果我们去正着摧毁 ，想想都有点困难，要不 我们使用逆向思维哈哈哈

2：没错 这道题就把摧毁转换成修建，然后利用并查集判断是否联通

#include <bits/stdc++.h>
#define f(i,a,b) for(register int i=a;i<=b;i++)
#define fd(i,a,b) for(register int i=a;i>=b;i--)using namespace std;
const int maxn=4e5+2;
int n,m,k,a,b,head[maxn],tot,total,broken[maxn],ans[maxn],father[maxn];
bool Broken[maxn];
struct edge
{int next,from,to;
}e[maxn];inline void add_edge(int u,int v)
{e[++tot].from=u;e[tot].next=head[