本文主要是介绍【tarjan缩点+小拓展】【POJ-2186】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用刚搞到的模板，去过了一道题
差不多是个模板题
有一群奶牛，奶牛A可以关注B，关注具有传递性，给出奶牛之间的关注关系，问有几只奶牛得到了所有其他奶牛的关注？
互相关注的可以看成一个点，所以直接tarjan算法 + 缩点
新图中，出度为0的点只能有一个，因为如果有两个，这两个新点（原连通分量）就一定是互相没有关注联系的
然后答案就是这个出度为0 的新点（原连通分量）中包含的原来点的个数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxm = 50050;vector <int> edge[maxm];
vector <int> now[maxm];
int hash[maxm];
int vis[maxm];
int dfn[maxm],Index;
int low[maxm];
int idx[maxm];
int ss[maxm],top;
bool InStack[maxm];
int inNum[maxm];
int n;
int nn;void dfs(int u)
{vis[u] = true;dfn[u] = low[u] = Index++;InStack[u] = true;ss[++top] = u;for(int i=0;i<edge[u].size();i++){int v = edge[u][i];if(!vis[v]){dfs(v);low[u] = min(low[u], low[v]);}else if(InStack[v])low[u] = min(low[u], dfn[v]);}if(low[u] == dfn[u]){nn++;int v = -1;while(u != v){v = ss[top--];InStack[v] = false;idx[v] = nn;inNum[nn]++;}}
}void tarjan()
{int i;memset(vis,0,sizeof(vis));memset(inNum,0,sizeof(inNum));Index = 1;top = 0;nn = 0;for(i=1;i<=n;i++){if(!vis[i]) dfs(i);}memset(hash,-1,sizeof(hash));for(i=1;i<=n;i++){for(int j=0;j<edge[i].size();j++){int v = edge[i][j];if(idx[i] != idx[v] && hash[idx[i]] != idx[v]){hash[idx[i]] = idx[v];now[idx[i]].push_back(idx[v]);}}}
}int main()
{freopen("input.txt","r",stdin);int m,i;while(scanf("%d%d",&n,&m) != EOF){for(i=0;i<maxm;i++) edge[i].clear();for(i=0;i<maxm;i++) now[i].clear();while(m--){int u,v;scanf("%d%d",&u,&v);edge[u].push_back(v);}tarjan();/*cout<<nn<<endl;for(i=1;i<=n;i++)cout<<i<<" now belong to "<<idx[i]<<endl;*/int flag = 0,ans;for(i=1;i<=nn;i++){if(now[i].size() == 0){flag++;ans = inNum[i];}}if(flag == 1)cout<<ans<<endl;else cout<<0<<endl;}return 0;
}
这篇关于【tarjan缩点+小拓展】【POJ-2186】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
