【图论】【思维】AGC011C Squared Graph

分析：

比较简单的思维题
首先，由于在新图中，每个点是原图的一个点对，观察这个新图中，两点间存在边的条件：
发现可以这么表示：在原图中又两个点$(i,j)$，分别向与其相邻的点走一步，到达$(u,v)$，那么$(i,j)$与$(u,v)$之间就有边相连。

这样表示在之后的推导中有重要意义。

假设我们考虑一个单一的联通块内部的情况：
首先，对于任意一个点对$(u,v)$，我们可以将两点均往中间缩，即$u$向$v$走一步，$v$向$u$走一步。
持续这样操作，最后只有2种情况:
1、$u,v$重合。（原本的路径长度为偶数）
2、$u,v$在一条边的两侧。（原本的路径长度为奇数）。

我们分别定义这两种情况为：点联通块，边联通块。
很显然，所有单点对$(i,i)$都在点联通块中，所有边都在边联通块中($(i,j)满足有边(i<?>j)$)

根据上面的推导，我们发现，整个原图的联通块，在新图中，就形成了2个联通块。但有种情况，会使得只有1个联通块。

观察我们上面的条件：路径长度分别为奇数，偶数。但如果联通块中有奇环，那么路径长度既可以有奇数，又可以有偶数。换言之，这一点对可以缩到点联通块中，又可以缩到边联通块中。所以，在这种情况下，这个联通块在新图中，就只有1个联通块。

现在考虑点对在两个联通块之间的情况：

有了上面的推导，不难发现这里其实也是一样的。对任意一个点对$(i,a)$
如果两联通块中均无奇环，那么这个点对就不可能连到$(i,b)$（b与a有边相连）。以及$(j,a)$（i与j有边相连）等等。因为如果i走了偶数步，又回到了i，同时a也必须走偶数步，如果没有奇环，那么a永远不可能走到与其相邻的某个点上。

所以，把结论综合一下，发现：
对任意两个联通块，如果其中一个有奇环，那么这两个联通块在新图中就连在一起。否则就形成互相交叉的两个联通块。

注意，对于单点的联通块需要特殊处理。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
struct node{
    int x;node *nxt;	
}edge[MAXN*4];
node *head[MAXN],*ncnt=edge;
void add_edge(int u,int v){
    ++ncnt;ncnt->x=v;ncnt->nxt=head[u];head[u]=ncnt;	
}
int fa[MAXN],n,m,tag[MAXN],dep[MAXN],siz[MAXN],tot;
int get_fa(int x){
    if(fa[x]==0)return x;fa[x]=get_fa(fa[x]);return fa[x];	
}
pair<int,int> l[MAXN*2];
void dfs(int x,int f){
    dep[x]=dep[f]^1;for(node *v=head[x];v!=NULL;v=v->nxt){
    int u=v->x;if(u==f)continue;dfs(u,x);}
}
ll cnt[2];
int main(){
    int u,v;SF("%d%d",&n,&m);for(int i=1;i<=n;i++)siz[i]=1;for(int i=1;i<=m;i++){
    SF("%d%d",&u,&v);if(get_fa(u)!=get_fa(v)){
    	add_edge(u,v);add_edge(v,u);u=get_fa(u);v=get_fa(v);fa[u]=v;siz[v]+=siz[u];}elsel[++tot]=make_pair(u,v);}for(int i=1;i<=n;i++)if(fa[i]==0)dfs(i,0);for(int i=1;i<=tot;i++)if(dep[l[i].first]==dep[l[i].second])tag[get_fa(l[i].first)]=1;	ll ans=0,poi=0;for(int i=1;i<=n;i++)if(fa[i]==0){
    if(siz[i]==1){
    ans+=n;poi++;}elsecnt[tag[i]]++;}ans+=(n-poi)*poi;ans+=cnt[1]*(cnt[1]+cnt[0]*2ll);ans+=cnt[0]*cnt[0]*2ll;PF("%lld",ans);}