这题我犯了一个逻辑错误，人傻了，想了半天也没debug出来；
做法：
是这样一个逻辑问题，一个点不是控制点，就是如果有控制点连到它就行了。
但，一个点是控制点，不是说连到它的点不是控制点就行了，只要有一个连到它的控制点，那它就不是控制点。
标准错误解法：
这个想法就是，vis=1表示他是控制点，如果一个点不是控制点，那么他的所有邻居就是控制点。
这肯定是错了，如果他的邻居有其他控制点可以连到呢？那这个邻居就不是控制点。
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; #define pb push_back bool vis[N]; int ans,in[N]; int n,m; vector<int>e[N]; void toposort(){ queue<int>Q; for(int i=1;i<=n;i++)if(in[i]==0)vis[i]=1,Q.push(i); while(!Q.empty()){ int u=Q.front();Q.pop(); if(vis[u])ans++; for(int i=0;i<e[u].size();i++){ int v=e[u][i]; if(!vis[u])vis[v]=1; if(--in[v]==0)Q.push(v); } } } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)in[i]=0,vis[i]=0; int a,b; while(m--){ scanf("%d %d",&a,&b); e[a].pb(b); in[b]++; } ans=0; toposort(); printf("%d\n",ans); return 0; }
正确解法：逻辑正确；
如果一个点是控制点，那么他的所有邻居就不是控制点。这个是正确的逻辑；】
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; #define pb push_back bool vis[N]; int ans,in[N]; int n,m; vector<int>e[N]; void toposort(){ queue<int>Q; for(int i=1;i<=n;i++)if(in[i]==0)Q.push(i); while(!Q.empty()){ int u=Q.front();Q.pop(); if(!vis[u])ans++; for(int i=0;i<e[u].size();i++){ int v=e[u][i]; if(!vis[u])vis[v]=1; if(--in[v]==0)Q.push(v); } } } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)in[i]=0,vis[i]=0; int a,b; while(m--){ scanf("%d %d",&a,&b); e[a].pb(b); in[b]++; } ans=0; toposort(); printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/littlerita/p/12442013.html
