强连通分量(Tarjan)

//P2002解题思路:
//先求SCC,缩点后,转换为DAG(有向无环图)
//在DAG上统计入度为0的scc数量即可 //Tarjan时间复杂度:O(N+E),每个点和每条边刚好被访问一次,在空间和时间上比Kosaraju好一些。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=500010;
struct edge{ int t; edge *nxt; edge(int to, edge * next){ t=to, nxt=next; } };
edge * h[maxn]; //h2是反图
void add(int u, int v){ h[u]=new edge(v, h[u]); }
int n, m, v[maxn], st[maxn], st_k, dfn[maxn], low[maxn], timestamp, sccno[maxn], scc_cnt, scc_indegree[maxn]; void tarjan(int x)
{
dfn[x]=low[x]=++timestamp;
st[++st_k]=x, v[x]=1; //v数组记录x是否在堆栈中
for(edge *p=h[x]; p; p=p->nxt)
{
if(!dfn[p->t]) tarjan(p->t), low[x]=min(low[x], low[p->t]); //通过dfn值判断点是否访问过
else if(v[p->t]) low[x]=min(low[x], low[p->t]); //通过v值判断该点是否在堆栈中
}
if(dfn[x]==low[x]) //发现SCC
{
sccno[x]=++scc_cnt; //scc计数,同时标记x
while(st[st_k]!=x)
{
sccno[st[st_k]]=scc_cnt;
v[st[st_k]]=0;
st_k--;
}
v[st[st_k--]]=0; //取消x在堆栈中的标记
}
} int main()
{
scanf("%d%d", &n, &m);
for(int i=1, b, e; i<=m; i++)
{
scanf("%d%d", &b, &e);
if(b!=e) add(b, e); //去除自环
}
for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
for(int i=1; i<=n; i++) //统计每个scc的入度
for(edge *p=h[i]; p; p=p->nxt)
if(sccno[i]!=sccno[p->t]) scc_indegree[sccno[p->t]]++; //起点和终点不在一个scc中才统计入度
int ans=0;
for(int i=1; i<=scc_cnt; i++) if(!scc_indegree[i]) ans++; //统计入度为0的scc的个数
printf("%d\n", ans);
return 0;
}
上一篇:JAVA常见知识点整理


下一篇:VMware vSphere Client的简单使用教程