Tarjan求SCC
板子题。
在dfs时给当前点dfs序,顺便加入栈,往下更新,如果没遍历,就先遍历在更新自己的low,如果已经遍历了,更新自己的low。
因为是dfs,所以SCC最下面的点的low就会被递归回去。然后到一个dfs序和low一样的点,那么就可以将此时栈里的点给缩了。
如果父亲节点和子节点的color(也就是缩了之后的点的序号)不同,他就不是那头最受欢迎的牛。
此题只能有一个SCC,如果有了两个就不行。
代码
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f
#define ll long long
#define eps 1e-5
int n,m,ans,deep,sum,top,tmp;
int cd[N*N],sta[N*N],low[N*N],dfn[N*N],cnt[N*N],clo[N*N];
bool vis[N*N];
vector<int> boy[N*N];
void tarjan(int u){
dfn[u]=++deep;
low[u]=deep;
vis[u]=1;
sta[++top]=u;
int len=boy[u].size();
for(int i=0;i<len;i++){
int v=boy[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(vis[v]) low[u]=min(low[u],low[v]);
}
}
if(dfn[u]==low[u]){
clo[u]=++sum;
vis[u]=0;
while(sta[top]!=u){
clo[sta[top]]=sum;
vis[sta[top--]]=0;
}
top--;
}
}
int main(){
scanf("%d%d",&n,&m);
int s,t;
for(int i=1;i<=m;i++){
scanf("%d%d",&s,&t);
boy[s].push_back(t);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++){
int len=boy[i].size();
for(int j=0;j<len;j++){
int v=boy[i][j];
if(clo[i]!=clo[v]){
cd[clo[i]]++;
}
}
cnt[clo[i]]++;
}
for(int i=1;i<=sum;i++){
if(cd[i]==0){
tmp++;
ans=cnt[i];
}
}
if(tmp==0) printf("0");
else{
if(tmp>1) printf("0");
else printf("%d",ans);
}
}
有个地方想不通,最后求出度为零的强连通分量内部点个数,y总说强连通分量内部的点都是可以互相到达的那么应该从终点(唯一一个出度为零的点)出发也可以达到强连通分量内部的其他点但是这和终点本身的定义就相互违背了不是吗