Description
在 \(n*n\) 的棋盘上给出 \(m\) 个黑点, 若 \((x,y)\),\((y,z)\) 都是黑点, 那么 \((z,x)\) 也会变成黑点, 求最后黑点的数量
题面 https://agc006.contest.atcoder.jp/tasks/agc006_f
Solution
把点 \((x,y)\) 看作一条从 \(x\) 到 \(y\) 的有向边
我们分析性质:
如果存在一个自环, 那么这个点所在的连通块就会变成一个完全图
原因是和这个点有单向边的点都会变成双向边, 有双向边之后就会形成自环, 那么就可以一直重复这个过程, 就变成了完全图
我们想办法判断图中有没有自环, 我们发现: 对原图进行三染色之后:
1. 如果产生了矛盾, 那么就有自环, 就会形成一个完全图, 这个连通块的答案就是点数的平方
2. 如果染色完成了, 那么算出产生的边的个数和原图边的个数就行了
对于第二种情况, 还需要一些性质:
首先如果 \(color[x]±1 \mod 3 =color[u]\) 且 \(x,u\) 在同一连通块内, 则一定有边存在
所以设 \(a[x]\) 表示颜色为 \(x\) 的点的数量, 答案就是 \(a[1]*a[2]+a[2]*a[3]+a[1]*a[3]\)
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=1e5+10;
- int n,m,head[N],nxt[N*2],to[N*2],num=0,c[N],E=0,a[4],dis[N*2];
- bool flag=0,vis[N*2];
- vector<int>S;
- inline void link(int x,int y,int z){
- nxt[++num]=head[x];to[num]=y;head[x]=num;dis[num]=z;}
- inline void dfs(int x){
- S.push_back(x);
- for(int i=head[x];i;i=nxt[i]){
- int u=to[i],t=c[x]+dis[i];
- if(!vis[i])vis[i]=1,E++;
- if(!t)t=3;if(t==4)t=1;
- if(c[u]){
- if(c[u]!=t)flag=1;
- }
- else c[u]=t,dfs(u);
- }
- }
- int main(){
- freopen("pp.in","r",stdin);
- freopen("pp.out","w",stdout);
- int x,y;ll ans=0;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- scanf("%d%d",&x,&y);
- link(x,y,1);link(y,x,-1);
- }
- for(int i=1;i<=n;i++){
- if(!c[i]){
- vector<int>().swap(S);c[i]=1;flag=0;E=0;
- dfs(i);
- memset(a,0,sizeof(a));
- for(int j=S.size()-1;j>=0;j--)a[c[S[j]]]++;
- if(flag)ans+=(ll)S.size()*S.size();
- else if(!a[1] || !a[2] || !a[3])ans+=E/2;
- else ans+=1ll*a[1]*a[2]+1ll*a[2]*a[3]+1ll*a[1]*a[3];
- }
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2685890.html