tarjan缩点板子题，实际上也没什么太多好讲的，因为每一个强连通分量里的任意一个节点知道消息后，整个强连通分量的每个节点都得知了消息，故将每个强连通分量缩成一个点，便于求解
那么最后判断答案的时候呢，我真的是被tj里什么什么入度为0什么的惊呆了，因为我不知道什么叫入度。。可能是我太弱了。。然后经过我不懈的努力，基本上入度指的就是有多少个非该节点自身存在的强连通分量中的节点指向该节点的个数，说人话就是在缩点过后有几个点指向该节点
1 #include<set> 2 #include<map> 3 #include<list> 4 #include<queue> 5 #include<stack> 6 #include<string> 7 #include<cmath> 8 #include<ctime> 9 #include<vector> 10 #include<bitset> 11 #include<memory> 12 #include<utility> 13 #include<cstdio> 14 #include<sstream> 15 #include<iostream> 16 #include<cstdlib> 17 #include<cstring> 18 #include<algorithm> 19 using namespace std; 20 const int N=500005; 21 22 stack <int> q; 23 int tot,n,m,num,ans; 24 int head[N],next[N],to[N],dfn[N],low[N],f[N]; 25 bool visit[N]; 26 27 int get(){//快读，不加的话超时一个点 28 char zy=getchar(); 29 int zyy=1,zzy=0; 30 while(zy>'9'||zy<'0'){ 31 if(zy=='-'){ 32 zyy=-1; 33 } 34 zy=getchar(); 35 } 36 while(zy<='9'&&zy>='0'){ 37 zzy=zzy*10+zy-'0'; 38 zy=getchar(); 39 } 40 return zyy*zzy; 41 } 42 43 inline int mi(int a,int b){return a<b?a:b;} 44 inline int ma(int a,int b){return a>b?a:b;} 45 46 inline void add(int u,int v){//链式前向星 47 next[++tot]=head[u]; 48 head[u]=tot; 49 to[tot]=v; 50 } 51 52 void tarjan(int u){//tarjan板子，并由缩点的预处理 53 dfn[u]=low[u]=++tot; 54 visit[u]=1; 55 q.push(u); 56 for(int i=head[u];i;i=next[i]){ 57 if(!dfn[to[i]]){ 58 tarjan(to[i]); 59 low[u]=mi(low[u],low[to[i]]); 60 } 61 else if(visit[to[i]]){ 62 low[u]=mi(low[u],low[to[i]]); 63 } 64 } 65 if(dfn[u]==low[u]){ 66 int v; 67 num++; 68 do{ 69 v=q.top(); 70 q.pop(); 71 visit[v]=0; 72 f[v]=num;//缩点的预处理 73 }while(v!=u&&!q.empty()); 74 } 75 } 76 77 int main(){ 78 n=get(); 79 m=get(); 80 for(int i=1;i<=m;i++){ 81 int u,v; 82 u=get(); 83 v=get(); 84 if(u!=v){//去除自环的情况 85 add(u,v); 86 } 87 } 88 tot=0; 89 for(int i=1;i<=n;i++){ 90 if(!dfn[i]){ 91 tarjan(i); 92 } 93 } 94 memset(visit,0,sizeof(visit)); 95 for(int i=1;i<=n;i++){ 96 for(int j=head[i];j;j=next[j]){ 97 if(f[i]!=f[to[j]]){ 98 visit[f[to[j]]]=true;//与其求入度，在本题中还不如直接表示是否有点指向自身，便于理解 99 } 100 } 101 } 102 for(int i=1;i<=num;i++){ 103 ans+=(!visit[i]);//表示没有节点指向自己，需要直接接收消息 104 } 105 printf("%d ",ans); 106 return 0; 107 }
那既然是缩点肯定还是有困难的，那既然有困难，就多做做吧嘤嘤嘤