AcWing 4415. 点的赋值
原题链接
困难
作者:
曦薇
,
2022-05-01 11:25:42
,
所有人可见
,
阅读 169
思路
- 类似二分图的做法。如果出现奇数边的环,那么就无解。
- 用 $bfs$ 遍历每一个连通块,对连通块中的每一个点标记上层次,如果同一层之间有边相连,则说明一定存在奇数边的环,结果为 $0$ 。如果一个连通块是合法的,我们就对他进行染色,分别考虑奇数层填偶数和奇数层填奇数两种情况,然后用加法原理求和;对于不同连通块的染色组合,用乘法原理求乘积。
- 注意对于不同的测试用例,一定不能用 $memeset$ 对数组重新初始化,因为一次 $memset$ 实时间复杂度为 $O(n)$ ;题目测试用例规定的数据最坏时间复杂度可能达到 $O(10^5 \times 10^5)$ ,一定会 $TLE$ 的。应该有多少个点对多少个点循环初始化。
- 时间复杂度为 $O(n+m)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int N=300010;
vector<int> v[N];
int st[N];
int n,m;
int ans1=0,ans2=0;
bool bfs(int x,int dis){
queue<int> q;
st[x]=dis;
q.push(x);
ans1=2,ans2=1;
while(!q.empty()){
int i,t=q.front();
dis=st[t]+1;
for(i=0;i<v[t].size();i++){
//cout<<t<<" "<<v[t][i]<<" "<<st[t]<<" "<<st[v[t][i]]<<" "<<(dis-1)<<endl;
if(st[v[t][i]]==dis-1) return false;
if(st[v[t][i]]==0){
st[v[t][i]]=dis;
q.push(v[t][i]);
if(dis%2) ans1=(ans1*2)%MOD;
else ans2=(ans2*2)%MOD;
}
}
q.pop();
}
return true;
}
int main(void){
int T;
scanf("%d",&T);
while(T--){
register int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
v[i].clear();
}
memset(st,0,sizeof st);
int u1,u2;
for(i=1;i<=m;i++){
scanf("%d%d",&u1,&u2);
v[u1].push_back(u2);
v[u2].push_back(u1);
}
int ans4=0,ans5=0;
int ff=1;
long long aaa=1;
for(i=1;i<=n;i++){
if(st[i]>0) continue;
if(!bfs(i,1)){
ff=0;
printf("0\n");
break;
}
//ans4=(ans4+ans1)%MOD,ans5=(ans5+ans2)%MOD;
int ans6=(ans1+ans2)%MOD;
aaa=(aaa*ans6)%MOD;
}
if(ff) printf("%lld\n",aaa);
}
return 0;
}