POJ 2186 Popular Cows

targan，图论

传送门：POJ

传送门：HustOJ

---

题意

给你一个图，如果A认为B很厉害，那么有一条A指向B的边。求被所有其他人都认为很厉害的人的数量。

---

思路

思路很简单，targan缩点，求出度为0的连通分量。

但是有几个问题，比如这组数据：

4 4 1 2 2 1 1 4 2 3

这样应该输出0，因为3和4不认为对方很厉害，所以没有这样的人。

还要考虑图不连通的情况，其实程序里面不连通和上面的数据是一种情况。

---

代码

#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <cmath> #include <queue> #include <stack> #include <map> #define _ ios_base::sync_with_stdio(0),cin.tie(0) #define M(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXN=10005; const int oo=0x3f3f3f3f; typedef __int64 LL; const LL loo=4223372036854775807ll; typedef long double LB; const LL mod=1e9+7; typedef long long LL; struct Targan { //sccno[i]为i所在的dfs块编号 vector<int> G[MAXN]; int pre[MAXN], lowlink[MAXN], sccno[MAXN], dfs_clock, scc_cnt; stack<int> S; void init() { for(int i=0;i<MAXN;i++) G[i].clear(); while(!S.empty()) S.pop(); } void addedge(int a, int b)//加边，单向边a到b { G[a].push_back(b); } void dfs(int u) { pre[u]=lowlink[u]=++dfs_clock; S.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!pre[v]) { dfs(v); lowlink[u]=min(lowlink[u], lowlink[v]); } else if(!sccno[v]) { lowlink[u]=min(lowlink[u], pre[v]); } } if(lowlink[u]==pre[u]) { scc_cnt++; while(true) { int x=S.top();S.pop(); sccno[x]=scc_cnt; if(x==u) break; } } } void find_scc(int n) { dfs_clock=scc_cnt=0; M(sccno, 0);M(pre, 0); for(int i=1;i<=n;i++)//注意修改取值范围 { if(!pre[i]) dfs(i); } } }; int oudegree[MAXN], indegree[MAXN]; int main() { _; int n; Targan targan; while(cin>>n) { targan.init(); M(oudegree, 0);M(indegree, 0); int m;cin>>m; for(int i=0;i<m;i++) { int a, b;cin>>a>>b; targan.addedge(a, b); } targan.find_scc(n); for(int i=1;i<=n;i++) { for(int j=0;j<targan.G[i].size();j++) { int to=targan.G[i][j]; if(targan.sccno[i]!=targan.sccno[to]) { oudegree[targan.sccno[i]]=1; indegree[targan.sccno[to]]=1; } } } vector<int> res; for(int i=1;i<=n;i++) { if(oudegree[targan.sccno[i]]==0) { res.push_back(i); } } int sum=0; for(int i=1;i<=targan.scc_cnt;i++) { if(oudegree[i]==0) sum++; } if(sum==1) cout<<res.size()<<endl; else cout<<0<<endl; } return 0; }