写了一晚上板子，无话可说
#include#include #include #include #include #include #include #include #include #include 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 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 > linefrom;vector > 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