首页 > 代码库 > XDOJ_1072_tarjan
XDOJ_1072_tarjan
http://acm.xidian.edu.cn/problem.php?id=1072
求关键边的数量,即强连通分量-1,直接tarjan模版。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> using namespace std; int n,m,dfn[10005],low[10005],num,cnt; vector<int> v[10005]; void tarjan(int pos,int pre) { dfn[pos] = low[pos] = ++num; for(int i = 0;i < v[pos].size();i++) { int x = v[pos][i]; if(x == pre) continue; if(dfn[x] == 0) { tarjan(x,pos); low[pos] = min(low[pos],low[x]); if(dfn[pos] < low[x]) cnt++; } else low[pos] = min(low[pos],dfn[x]); } } int main() { int T; scanf("%d",&T); while(T--) { num = 0; cnt = 0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); scanf("%d%d",&n,&m); for(int i = 0;i < n;i++) v[i].clear(); while(m--) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } tarjan(0,-1); printf("%d\n",cnt); } return 0; }
XDOJ_1072_tarjan
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。