Submission #1574282

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 100000
#define MAXM 400000
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
int first[MAXN+5], con[MAXN+5], book[MAXN+5], sz[MAXN+5], N, M, I, B, G, tot; bool unbi[MAXN+5];
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex):to(_to),nex(_nex){}}e[MAXM+5];
inline void Add(int a, int b){e[tot] = Edge(b,first[a]), first[a] = tot++, e[tot] = Edge(a,first[b]), first[b] = tot++;}
void DFS(int p, int w){book[p] = w; ++sz[G]; for(rint u = first[p], v; ~u; u = e[u].nex) if(!book[v=e[u].to]) DFS(v,w^1); else if(book[v] == w) B -= !unbi[G], unbi[G] = true;}
int main()
{
	N = read(), M = read(), memset(first+1,-1,N<<2); for(rint i = 1; i <= M; Add(read(),read()), i++);
	for(rint i = 1; i <= N; book[i] ?: (DFS(con[++G]=i,2),0), I += sz[G]==1, i++); G -= I, B += G, G -= B;
	printf("%lld\n",2ll*I*N-1ll*I*I+1ll*G*G+2ll*G*B+2ll*B*B); return 0;
}

Submission Info

Judge Result