题目链接：https://vijos.org/p/1023
最近在练强联通分量，当然学的是tarjan算法
而这一道题虽然打着难度为3，且是tarjan算法的裸题出没在vijos里面
但其实并不是纯粹只需要tarjan求有几个强联通就可以过的（我以为这是所谓的裸题）
其实这题还需要对每一个强联通缩点，可能被所谓裸题误导的OIer们看不破这个
毕竟，这个样例数据也是坑啊，样例数据都可以说是无向图了，哪里还是什么有向图
所以样例数据不是万能的，但是没过样例数据是万万不能的
至于为什么缩点我们来想一想，这张图中，怎么才满足可以被通知到
是在一个强联通分量里面？还是有一条边相连？还是有别的人指向他？
当然可以想到是有人指向他，这样就可以排除求出强联通分量个数的方法。。
不过我们可以确认的是，在一个强联通分量的点，只需要一个点就可以把这个强联通分量通知完，然后我们就可以判断任意两个强联通分量有没有可能有联系，也就是刚刚提到的有没有指向这个强联通分量的其他分量，也就是有没有入度。如果有入度，我们就可以把这个强联通分量与另一个合并，也就是这两个分量只要一个人就可以通知完。由于在这里理解成强联通分量会有些麻烦，所以就是所谓的缩点，把这个强联通分量看成一个点再来找边和入度
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define maxn 20510 using namespace std;11 12 struct node{13 int u,v,w,nxt;14 }e[maxn*maxn];15 16 int head[maxn],dfn[maxn],low[maxn],belong[maxn];17 int num,tot,n,m,k,ans,in[maxn],cnt;18 stack s;19 20 void adde(int u,int v){21 e[++tot].u=u;22 e[tot].v=v;23 e[tot].nxt=head[u];24 head[u]=tot;25 }26 27 void tarjan(int u){28 num++;29 dfn[u]=low[u]=num;30 s.push(u);31 for(int i=head[u];i!=-1;i=e[i].nxt){32 int v=e[i].v;33 if(dfn[v]==0){34 tarjan(v);35 low[u]=min(low[u],low[v]);36 }else{37 if(!belong[v])low[u]=min(low[u],dfn[v]);38 }39 }40 if(dfn[u]==low[u]){41 ans++;42 belong[u]=ans;43 while(s.top()!=u){44 belong[s.top()]=ans;45 s.pop(); 46 }s.pop();47 }48 }49 50 int main(){51 memset(head,-1,sizeof(head));52 scanf("%d",&n);53 for(int i=1;i<=n;i++){54 int a;scanf("%d",&a);55 while(a!=0){56 adde(i,a);scanf("%d",&a);}57 }58 for(int i=1;i<=n;i++){59 if(dfn[i]==0)tarjan(i);60 }61 for(int i=1;i<=tot;i++){62 int u=e[i].u,v=e[i].v;63 if(belong[u]!=belong[v]){64 in[belong[v]]++;65 }66 }67 for(int i=1;i<=ans;i++){68 if(!in[i])cnt++;69 }70 printf("%d",cnt);71 }
【总结】
样例数据是万能的，不能过于相信样例，但是样例错了那就肯定错了
(另外，之前看见有人说原本想并查集但是错了，我个人没有想通为何不能简单的用并查集来偷懒，希望大佬能指点我一番)