1 条题解
-
0
// Tarjan算法 O(n+m) #include<bits/stdc++.h> using namespace std; const int N=10010; int n,m,ans; vector<int> e[N]; int dfn[N],low[N],tim,stk[N],top,scc[N],siz[N],cnt; void tarjan(int u){ dfn[u]=low[u]=++tim; stk[++top]=u; for(int v:e[u]){ if(!dfn[v]){ //若v尚未访问 tarjan(v); low[u]=min(low[u],low[v]); } else if(!scc[v]) //若v已访问且未构成SCC low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ //若u不是SCC的根,则low<dfn ++cnt; for(int v=-1;v!=u;){ v=stk[top--]; scc[v]=cnt; //SCC的编号 ++siz[cnt]; //SCC的大小 } } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int a,b;m--;) cin>>a>>b,e[a].push_back(b); for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i); for(int i=1;i<=cnt;i++)if(siz[i]>1) ans++; cout<<ans; }
- 1
信息
- ID
- 2616
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 6
- 上传者