原试题点击此处
强连通分量概念: 强连通分量中的结点能够相互到达。
Tarjan算法思想:
两条腿走路:
一条腿深搜下去 一条腿回看(能不能回到自己本身)每次深搜/回看完了以后,都要更新一下low值。
用stack栈来记录强连通分量中具体的点:
1、每访问一次结点,就让结点入栈。
2、遇到dfn=low的点(即能从自己出发回到自己的点,可以看做强连通分量的根),
开始不断从栈顶弹出元素,直到dfn=low的点也出了栈(即让强连通分量出栈)。
Tarjan算法详解点击此处
代码如下
#include
#include
#include
#include
using namespace std;
const int N = 10005;
int n,m,top=0,index=0,ans=0,dfn[N]={0},low[N]={0},stk[N]={0},inStk[N]={0};
vector v[N];
void tarjan(int root){
if(dfn[root]) return;
dfn[root]=low[root]=++index;
stk[++top]=root;
inStk[root] = 1;
for(int i = 0; i < v[root].size(); i++){
int k = v[root][i];
if(!dfn[k]){
tarjan(k);//dfs过程
low[root]=min(low[root],low[k]);//回溯的时候更新一下low值
}else if(inStk[k]){//能指向时间戳更小的点
low[root]=min(low[root],low[k]);
}
}
if(low[root]==dfn[root]){
int sum = 0;
while(1){
int x = stk[top--];
inStk[x] = 0;
sum++;
if(x==root) break;
}
ans += (sum*(sum-1))/2;
}
}
int main()
{
int a,b;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d%d", &a, &b);
v[a].push_back(b);
}
for(int i = 1; i <= n; i++){
if(!dfn[i])
tarjan(i);
}
printf("%d\n", ans);
return 0;
}