[图论记录]AT2167 [AGC006F] Blackout
command_block
2021-01-12 15:39:30
**题意** ： 有 $n\times n$ 的矩阵，初始时有 $m$ 个格子是黑的。
若 $(x,y),(y,z)$ 都是黑色，则可以把 $(x,z)$ 涂黑。
问最终有多少个黑色格子。
$n,m\leq 10^5$ ，时限 $\texttt{2s}$。
------------
转化成一个更容易理解的题意 ：有一个 $N$ 个点的有向图，若有连边 $u\rightarrow v\rightarrow t$ 则可连边 $t\rightarrow u$。（即自动补全三元环）
问最终的边数。
显然需要对每个弱连通块分别处理。
手玩能发现，若是一条链，则会有三轮的规律。
每个红点会向所有绿点连边，每个绿点会向所有蓝点连边，每个蓝点会向所有红点连边。
若是二分图，则不会有多余的边。
若是非三倍数的环，则会形成完全图。
总结一下规律 ：
对图进行三染色，若染色成功且需要三种颜色，则最终形成一个三分图，图中的每一部分都向下一部分连边。
- **证明** ： 若染色成功，则显然不能再得到三分图之外的边。
我们停止加边只有可能是这样一种情况 ：对于所有异色三元组，要么已经形成三元环，要么只有不超过一条边。
不难发现此时图必然不是弱连通的。
若三染色失败，必然形成完全图。
- **证明** ： 先忽略导致染色冲突的边，建立三分图。然后加入这些边，一条错误的边在三分图中必然导出一个二元环。
二元环可以产生自环，而自环会进一步导出二元环。如此往复不难发现最终会得到完全图。
若需要的颜色不足三种，则不能加入任何边。这个比较显然。
综上，我们对每个弱连通块分别处理 ：
- 若三染色失败，贡献为 $siz^2$.
- 若三染色成功，且需要三种颜色，设三种颜色用量分别为 $r,g,b$ 则贡献为 $rg+gb+rb$。
- 若只需要不足三种颜色，则贡献为原来的边数。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 100500
using namespace std;
vector<int> g[MaxN],g2[MaxN];
int col[MaxN],p[MaxN],tn;
void dfs(int u)
{
p[++tn]=u;
for (int i=0;i<g[u].size();i++)
if (g[u][i]!=u&&!col[g[u][i]]){
col[g[u][i]]=col[u]%3+1;
dfs(g[u][i]);
}
for (int i=0;i<g2[u].size();i++)
if (g2[u][i]!=u&&!col[g2[u][i]]){
col[g2[u][i]]=(col[u]+1)%3+1;
dfs(g2[u][i]);
}
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g2[v].push_back(u);
}
long long ans=0;
for (int i=1;i<=n;i++)if (!col[i]){
tn=0;col[i]=1;dfs(i);
bool fl=1;
int c1=0,c2=0,c3=0,cm=0;
for (int j=1;j<=tn;j++){
int u=p[j];
c1+=col[u]==1;c2+=col[u]==2;c3+=col[u]==3;
cm+=g[u].size();
for (int i=0;i<g[u].size();i++)
if (col[g[u][i]]!=col[u]%3+1)fl=0;
}
if (!fl)ans+=1ll*tn*tn;
else if (!c2||!c3)ans+=cm;
else ans+=1ll*c1*c2+1ll*c2*c3+1ll*c3*c1;
}printf("%lld",ans);
return 0;
}
```