首页 > 代码库 > POJ 3180-The Cow Prom (图论-有向图强联通tarjan算法)
POJ 3180-The Cow Prom (图论-有向图强联通tarjan算法)
题目大意:有n个牛在一块, m条单项绳子, 有m个链接关系, 问有多少个团体内部任意两头牛可以相互可达
解题思路:有向图强连通分量模版图
代码如下:
#include<stdio.h>#include<vector>#include<map>#include<set>#include<algorithm>using namespace std;typedef long long ll;const int N = 10003;vector<int>G[N], DQ;int low[N], dfn[N], tot;bool mk[N];int n, m, ans;void init(){ ans = tot = 0; DQ.clear(); for(int i=1; i<=n; ++ i) { G[i].clear(); low[i] = dfn[i] = -1; mk[i] = false; }}void tarjan(int u, int f){ dfn[u] = low[u] = ++ tot; DQ.push_back(u); mk[u] = true; for(int i = 0; i<G[u].size(); ++ i) { int v = G[u][i]; if(dfn[v] == -1) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if(mk[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]) { int s; int k = 0; do { s = DQ.back(); k ++; DQ.pop_back(); mk[s] = false; } while(u != s); if(k > 1) ans ++; }}void solve(){ for(int i=1; i<=n; ++ i) { if(dfn[i] == -1) tarjan(i, -1); } printf("%d\n", ans);}int main(){ while(~scanf("%d%d", &n, &m)) { init(); for(int i=1; i<=m; ++ i) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); } solve(); } return 0;}
POJ 3180-The Cow Prom (图论-有向图强联通tarjan算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。