layout: post
title: 训练指南 UVALive - 4287 （强连通分量+缩点）
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 强连通分量
- 图论
- 训练指南
Proving Equivalences
题意
有n个命题，已知其中的m个推导，要证明n个命题全部等价（等价具有传递性），最少还需要做出几次推导。
题解
由已知的推导可以建一张无向图，则问题变成了最少需要增加几条边能使图变成强连通图。找出所有的强连通分量，将每一个连通分量视作一个大节点，则整张图变成了一张DAG。设出度为0的大节点个数为a，入度为0的大节点个数为b，则答案就是max(a,b)。为什么是这样呢？因为要使等价证明前进下去，每个大节点的出度和入度都必须不能是0。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>G[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int>S;
void dfs(int u){
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!pre[v]){
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!sccno[v]){
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if(lowlink[u]==pre[u]){
scc_cnt++;
for(;;){
int x=S.top();S.pop();
sccno[x]=scc_cnt;
if(x==u)break;
}
}
}
void find_scc(int n){
dfs_clock=scc_cnt=0;
memset(sccno,0,sizeof(sccno));
memset(pre,0,sizeof(pre));
for(int i=0;i<n;i++)
if(!pre[i])dfs(i);
}
int in[maxn],out[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)G[i].clear();
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;u--;v--;
G[u].push_back(v);
}
find_scc(n);
for(int i=1;i<=scc_cnt;i++)in[i]=out[i]=1;
for(int u=0;u<n;u++)
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(sccno[u]!=sccno[v])in[sccno[v]]=out[sccno[u]]=0;
}
int a=0,b=0;
for(int i=1;i<=scc_cnt;i++){
if(in[i])a++;
if(out[i])b++;
}
if(scc_cnt==1)cout<<0<<endl;
else cout<<max(a,b)<<endl;
}
return 0;
}