[??记录]AT2339 [AGC011C] Squared Graph

**题意** : 给定一张有 $n$ 个点 ，$m$ 条边的无向图图 $G$，现构造一张新图 $G'$，其中每个点都是一个二元组$(a, b)$。 点 $(a, b),(c, d)$ 之间有边当且仅当 $G$ 中 $a$ 和 $c$ 有边且 $b$ 和 $d$ 有边。 求 $G'$ 中的联通块个数。 $n\leq 10^5,m\leq 2\times 10^5$ ，时限 $\texttt{2s}$。 ------------ 可以抽象成 ： 有两个小人，一个在 $u$ 点，一个在 $v$ 点，以 $(u,v)$ 来描述他们的状态。 每轮操作中，两人可以同时行动一步。若两个状态可以在操作若干次之后相同，则在同一个等价类中，求等价类的个数。 首先查看 $G$ 中的孤立点。对于孤立点 $u$ ，所有与 $u$ 相关的状态都是无法转移的。 若有 $c$ 个孤立点，则贡献为 $n^2-(n-c)^2$。 现在考虑非孤立点 $u,v$。 若 $u$ 所在的联通块内存在奇环，则 $u$ 前往奇环绕一圈再回来， $v$ 左右横跳，即可制造出 $u$ 或者 $v$ 单走一步的效果。这样，两个联通块之间的点对都在同一等价类之内。 若 $u,v$ 所在的联通块内都不存在奇环，则黑白染色，每操作一次会将两个点的颜色都取反。 则分为两个等价类 ： $(\text{黑},\text{白})+(\text{白},\text{黑}),\ (\text{黑},\text{黑})+(\text{白},\text{白})$。 统计有奇环的联通块个数 $c_1$ ，无奇环的联通块个数 $c_2$ ，贡献为 $(c_1+c_2)^2+c_2^2$。 复杂度 $O(n+m)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define MaxN 100500 using namespace std; vector<int> g[MaxN]; bool fl,c[MaxN],vis[MaxN]; void dfs(int u) { vis[u]=1; for (int i=0,v;i<g[u].size();i++) if (!vis[v=g[u][i]]){ c[v]=!c[u]; dfs(v); }else if (c[v]==c[u])fl=0; } int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); g[u].pb(v);g[v].pb(u); } int c0=0,c1=0,c2=0; for (int i=1;i<=n;i++) if (!vis[i]){ if (!g[i].size()){c0++;continue;} fl=1;dfs(i); if (fl)c2++;else c1++; } printf("%lld",1ll*n*n-1ll*(n-c0)*(n-c0)+1ll*(c1+c2)*(c1+c2)+1ll*c2*c2); return 0; } ```