bzoj1051: [HAOI2006]受欢迎的牛
若A喜欢B则连一条边，求强联通分块，设出度为零的块数为C，若C>1则误解，C=1则输出块数
const int N = 10010, M = 50010;struct Edge {int v;Edge *Next;Edge() {}Edge(int _v, Edge *_Next) : v(_v), Next(_Next) {}} *Fir[N];int n, m;inline void Ins(int u, int v) {Fir[u] = new Edge(v, Fir[u]);}inline void Input() {scanf("%d%d", &n, &m);For(i, 1, n) Fir[i] = NULL;For(i, 1, m) {int u, v;scanf("%d%d", &u, &v), Ins(u, v);}}int dfn[N], low[N], belong[N], tot, T;bool Instack[N];int Out[N];stack<int> sta;inline void tarjan(int x) {dfn[x] = low[x] = ++T, sta.push(x), Instack[x] = 1;for(Edge *Tab = Fir[x]; Tab != NULL; Tab = Tab->Next) {int v = Tab->v;if(dfn[v] == -1) {tarjan(v);low[x] = min(low[x], low[v]);} else if(Instack[v]) low[x] = min(low[x], dfn[v]);}if(dfn[x] == low[x]) {++tot;while(sta.top() != x) {int v = sta.top();belong[v] = tot, sta.pop(), Instack[v] = 0;}belong[x] = tot, Instack[x] = 0, sta.pop();}}inline void Solve() {// rebuildclr(dfn, 255), clr(Instack, 0), tot = T = 0;while(sz(sta)) sta.pop();For(i, 1, n)if(dfn[i] == -1) tarjan(i);// CheckFor(i, 1, tot) Out[i] = 0;For(i, 1, n)for(Edge *Tab = Fir[i]; Tab != NULL; Tab = Tab->Next) {int v = Tab->v;if(belong[v] ^ belong[i]) {Out[belong[i]] = 1;break;}}int Which = -1, Check = 0;For(i, 1, tot)if(!Out[i]) {if(!Check) Which = i, Check = 1;else if(Check) {Which = -1;break;}}int Ans = 0;For(i, 1, n) Ans += (belong[i] == Which);printf("%d\n", Ans);}int main() { #ifndef ONLINE_JUDGE SETIO("1051"); #endif Input(); Solve(); return 0;}?