seo关键词如何布局,seo顾问服务 品达优化,网站建设得多钱,网站建设金手指专业正题
题目链接:https://www.luogu.com.cn/problem/AT2339 题目大意
给出nnn个点mmm条边的一张无向图#xff0c;然后有一张nnn\times nnn的图#xff0c;每个点是一个二元组(a,b)(a,b)(a,b)。(a,b)(a,b)(a,b)和(c,d)(c,d)(c,d)连边当且仅当aaa和ccc有连边#xff0c;bbb和…正题
题目链接:https://www.luogu.com.cn/problem/AT2339 题目大意
给出nnn个点mmm条边的一张无向图然后有一张n×nn\times nn×n的图每个点是一个二元组(a,b)(a,b)(a,b)。(a,b)(a,b)(a,b)和(c,d)(c,d)(c,d)连边当且仅当aaa和ccc有连边bbb和ddd有连边。
求新图的连通块数量
1≤n≤105,1≤m≤2×1051\leq n\leq 10^5,1\leq m\leq 2\times 10^51≤n≤105,1≤m≤2×105 解题思路
计数问题我们考虑固定一个基准以原图中的连通块为基准。
对于一个点(x,y)(x,y)(x,y)它能走到的点发现如果xxx和yyy所在的连通块都可以黑白染色那么xxx和yyy的黑白顺序是固定的否则无论如何xxx整个都可以变为整个连通块或者yyy可以变为整个连通块。
然后这样一些会发现样例都过不了因为有一种很特殊的点就是没有任何边连接的点这一部分的点我们需要特判。
记大小不是111的连通块数为AAA其中能奇偶染色的为BBB大小为111的连通块数为CCC那么答案就是 A×AB×BC×n×2−C×CA\times AB\times BC\times n\times 2-C\times CA×AB×BC×n×2−C×C
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510;
struct node{ll to,next;
}a[N1];
ll n,m,tot,siz,A,B,C,ls[N],v[N];
bool flag;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll c){if(v[x](c^1))flag1;if(v[x]0)return;v[x]c;siz;for(ll ils[x];i;ia[i].next)dfs(a[i].to,c^1);return;
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1,x,y;im;i){scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}memset(v,-1,sizeof(v));for(ll i1;in;i)if(v[i]0){flagsiz0;dfs(i,0);if(siz1)C;else A,B!flag;}printf(%lld\n,1ll*A*A1ll*B*B2ll*C*n-C*C);return 0;
}
