写了一晚上板子，无话可说
#include <iostream> #include <cstdio> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <set> using namespace std; #define hh printf("--------------\n"); const int maxn=20000+100; const int maxm=50000+100; int low[maxn],dfn[maxn]; int ncnt,ccnt; int noc[maxn]; int hade[maxm]; bool vis[maxn],insk[maxn]; stack<int> sk; struct note { int to; int next; } aa[maxm]; int n,m,k; void addage(int fr,int to) { aa[k].to=to; aa[k].next=hade[fr]; hade[fr]=k++; } void tarjan(int u) { ncnt++; low[u]=ncnt; dfn[u]=ncnt; sk.push(u); vis[u]=1; insk[u]=1; for(int i=hade[u]; i!=-1; i=aa[i].next) { int v=aa[i].to; if(!vis[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(insk[v]) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) { int v; do { v=sk.top(); sk.pop(); insk[v]=0; noc[v]=ccnt; } while(v!=u); ccnt++; } } vector<set<int> > linefrom; vector<set<int> > lineto; void yasuo(int nn,int nc) { linefrom.resize(nc); lineto.resize(nc); for(int u=1; u<=nn; u++) for(int i=hade[u]; i!=-1; i=aa[i].next) { int v=aa[i].to; int cu=noc[u]; int cv=noc[v]; if(cu!=cv) { linefrom[cv].insert(cu); lineto[cu].insert(cv); } } } void init() { k=0; memset(hade,-1,sizeof(hade)); memset(vis,0,sizeof(vis)); memset(insk,0,sizeof(insk)); memset(aa,0,sizeof(aa)); memset(noc,0,sizeof(noc)); while(sk.size()) sk.pop(); linefrom.clear(); lineto.clear(); ncnt=0; ccnt=0; } int t; int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); int a,b; for(int i=1; i<=m; i++) { scanf("%d%d",&a,&b); addage(a,b); } for(int i=1; i<=n; i++) if(!vis[i]) tarjan(i); yasuo(n,ccnt); int z_in=0,z_out=0; for(int i=0; i<ccnt; i++) { if(linefrom[i].empty()) z_in++; if(lineto[i].empty()) z_out++; } int mm=max(z_in,z_out); if(ccnt==1) mm=0;//注意，如果只有一个点，那么它的连通分量也是1，但出入度为1，但结果应该是0 printf("%d\n",mm); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7512127.html
