1 条题解
-
-27
#include<bits/stdc++.h> using namespace std; int n,m; vector<int>a[100005],g[100005]; stack<int> st; int h[100005],dfn[100005],low[100005],f[100005],times,cnt,fa[100005]; vector<int>b[100005]; void dfs(int u){ dfn[u]=low[u]=++times; h[u]=1;st.push(u); for(int i=0;i<a[u].size();i++){ int v=a[u][i]; if(dfn[v]==0){ dfs(v); low[u]=min(low[u],low[v]); }else if(h[v]==1)low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ if(st.top()!=u)cnt++; while(st.top()!=u){ f[st.top()]=cnt; b[cnt].push_back(st.top()); h[st.top()]=0; st.pop(); } f[st.top()]=cnt; b[cnt].push_back(st.top()); h[st.top()]=0; st.pop(); } } int mian(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; a[u].push_back(v); } for(int i=1;i<=n;i++){ dfs(i); } dfs(1); cout<<cnt; return 0; }
信息
- ID
- 485
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 398
- 已通过
- 75
- 上传者