缩点—tarjan求强连通分量scc的应用
注意
需要注意的是做完$tarjan$算法之后,拓扑序一定是按照强连通分量节点编号递减的顺序,不需要再做一遍拓扑排序
强连通分量的定义 : 简单来说说就是一个有向的环
题意解析
思路
题目中初始给出的图不是一张完整的图,而是给出条件:
如果$A->B$,$B->C$,那么$A$与$C$就是联通的, 所以我们可以根据这个依据来建图,我的第一反应就是传递闭包,但是很明显${n}^{3}$的时间复杂度会超时
我们发现如果题目中不存在环的情况下,只存在一个出度为0的点,那么点就是题目中符合题意的点,那么我们有没有办法将初始的图转化成一张不含任何环的拓扑图呢。
那么就引入缩点的思想了,求出初始图中所有的强连通分量,并且将这些强连通分量都看成是一个点(因为强连通分量内部的点可以互相到达,所以可以将它看成是一个整体)
那么求解转化后的图,找出所有出度为0的点,如果只存在一个,那么说明那个强连通分量的所有点都是符合要求的,如果存在多个,那么图中就不存在符合要求的点。
tarjan算法求scc详解
tarjan的核心变量:
$low[u]$ : 表示从$u$开始走(遍历它的子树),所能遍历到的最小时间戳是什么(u节点当前所在强连通块的最高点)。
最高指的是强连通分量中最先被遍历的点
$dnt[u]$ :表示遍历到$u$的时间戳
$timestamp$: 表示每个结点第一次被访问的时间,赋值为$1 ~ n$
栈sta: 栈代表当前未被搜完的强连通分量的所有点
in_sta[i] : 表示$i$节点是否在栈中
完整遍历完一个强连通分量的标志是:
$low[u] == dnt[u]$ ,表示当前遍历回了所在连通块的最高点,那么就从当前点$u$开始遍历将所在联通块的所有节点都记录下来
low[u]更新的条件是:
1. !dnt[j] (未被遍历过的节点):
$j$也许存在反向边到达比$u$还高的层,所以用$j$能到的最小$dnt$序(最高点)更新u能达到的(最小$dnt$序)最高点
/*
u是当前遍历的节点,j是u邻接的节点
*/
low[u] = min(low[u],low[j]);
2.如果已经在栈中,说明出现了横插边和反向遍历回了已经遍历过的节点
low[u] = min(low[u],dnt[j]);
缩点—强连通分量的应用
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 10010,M = 50010;
int h[N],e[M],ne[M],idx;
int dnt[N]; //表示遍历到u的时间戳
int low[N]; //low[u]表示从u开始走(遍历它的子树),所能遍历到的最小时间戳是什么(u节点当前所在强连通块的最高点)。
int timestamp; //表示每个结点第一次被访问的时间,赋值为1 ~ n
stack<int> sta; //栈代表当前未被搜完的强连通分量的所有点
bool in_sta[N]; //in_sta[i]表示i节点是否在栈中
int id[N]; //id[i]表示编号为i节点的强连通块编号
int size_scc[N]; //强连通块块的大小
int scc_cnt; //强连通块的编号
int dout[N];
int n,m;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void tarjan(int u){
low[u] = dnt[u] = ++timestamp;
sta.push(u); in_sta[u] = true;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(!dnt[j]){ //j没被遍历过
//j也许存在反向边到达比u还高的层,所以用j能到的最小dfn序(最高点)更新u能达到的(最小dfn序)最高点
tarjan(j);
low[u] = min(low[u],low[j]);
//如果已经在栈中,说明出现了横插边和反向遍历回了已经遍历过的节点
}else if(in_sta[j]){
low[u] = min(low[u],dnt[j]);
}
}
/*
→ u
/ /
/ ne1
← ne2
*/
//说明回到了强连通块的最高点,那么就将这个强连通块的所有节点进行缩点
if(low[u] == dnt[u]){
int y;
scc_cnt++;
do{ //按dfs的顺序搜索,强连通块的最高点在栈底,所以一直出栈直到u即为强连通块的所有节点
y = sta.top();
sta.pop();
in_sta[y] = false;//则y不再在栈中
id[y] = scc_cnt;
size_scc[scc_cnt]++;
}while(y != u);
}
}
int main(){
cin >> n >> m;
memset(h,-1,sizeof h);
for(int i = 0;i < m;++i){
int a,b;
cin >> a >> b;
add(a,b);
}
//找出强连通块,并且将强连通块缩成一个点
for(int i = 1;i <= n;++i){
if(!dnt[i]) tarjan(i);
}
//由强连通块形成的图即是一个拓扑图,统计每个节点所在强连通块的出度
for(int i = 1;i <= n;++i){
for(int j = h[i];j != -1;j = ne[j]){
int k = e[j];
int a = id[i] , b = id[k];
if(a != b) dout[a]++; //强连通块a->b , a的出度 + 1
}
}
//如果只有一个出度为0的强连通分量,那这个分量内的所有点都能够被
int zeros = 0; //出度为0点的数量
int res = 0;
for(int i = 1;i <= scc_cnt;++i){ //遍历所有强连通块
if(dout[i] == 0){
zeros++;
res += size_scc[i]; //联通分量的所有节点都满足要求
if(zeros > 1){
res = 0;
break;
}
}
}
printf("%d\n",res);
return 0;
}
传递闭包做法(超时)
c++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010 , M = 50010;
int g[N][N]; //原图数组
//i->j表示i认为j是受欢迎的
int d[N][N]; //传递闭包数组,d[i][j]表存在一条i->j
int n,m;
void floyd(){ //传递闭包的过程
//memcpy(d,g,sizeof d);
for(int k = 1;k <= n;++k){
for(int i = 1;i <= n;++i){
for(int j = 1;j <= n;++j){
//a->b , b->c ====> a->c
if(d[i][k] && d[k][j]){
d[i][j] = 1;
}
}
}
}
}
int check(){
int res = 0;
for(int j = 1;j <= n;++j){
bool flag = true;
for(int i = 1;i <= n;++i){
if(i == j) continue;
if(d[i][j] == 0){
flag = false;
//cout << i <<' ' << j << endl;
break;
}
}
if(flag) res++;
}
return res;
}
int main(){
cin >> n >> m;
for(int i = 0;i < m;++i){
int a,b;
cin >> a >> b;
d[a][b] = 1;
}
floyd();
int res = check();
printf("%d\n",res);
return 0;
}
神牛!谢德态嚎辣!(怒吼!甩头咆哮!)