题目链接：https://vijos.org/p/1023
最近在练强联通分量，当然学的是tarjan算法
而这一道题虽然打着难度为3，且是tarjan算法的裸题出没在vijos里面
但其实并不是纯粹只需要tarjan求有几个强联通就可以过的（我以为这是所谓的裸题）
其实这题还需要对每一个强联通缩点，可能被所谓裸题误导的OIer们看不破这个
毕竟，这个样例数据也是坑啊，样例数据都可以说是无向图了，哪里还是什么有向图
所以样例数据不是万能的，但是没过样例数据是万万不能的
至于为什么缩点我们来想一想，这张图中，怎么才满足可以被通知到
是在一个强联通分量里面？还是有一条边相连？还是有别的人指向他？
当然可以想到是有人指向他，这样就可以排除求出强联通分量个数的方法。。
不过我们可以确认的是，在一个强联通分量的点，只需要一个点就可以把这个强联通分量通知完，然后我们就可以判断任意两个强联通分量有没有可能有联系，也就是刚刚提到的有没有指向这个强联通分量的其他分量，也就是有没有入度。如果有入度，我们就可以把这个强联通分量与另一个合并，也就是这两个分量只要一个人就可以通知完。由于在这里理解成强联通分量会有些麻烦，所以就是所谓的缩点，把这个强联通分量看成一个点再来找边和入度
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstdlib>
#define maxn 205
using namespace std; struct node{
int u,v,w,nxt;
}e[maxn*maxn]; int head[maxn],dfn[maxn],low[maxn],belong[maxn];
int num,tot,n,m,k,ans,in[maxn],cnt;
stack<int >s; void adde(int u,int v){
e[++tot].u=u;
e[tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
} void tarjan(int u){
num++;
dfn[u]=low[u]=num;
s.push(u);
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].v;
if(dfn[v]==){
tarjan(v);
low[u]=min(low[u],low[v]);
}else{
if(!belong[v])low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
ans++;
belong[u]=ans;
while(s.top()!=u){
belong[s.top()]=ans;
s.pop();
}s.pop();
}
} int main(){
memset(head,-,sizeof(head));
scanf("%d",&n);
for(int i=;i<=n;i++){
int a;scanf("%d",&a);
while(a!=){
adde(i,a);scanf("%d",&a);}
}
for(int i=;i<=n;i++){
if(dfn[i]==)tarjan(i);
}
for(int i=;i<=tot;i++){
int u=e[i].u,v=e[i].v;
if(belong[u]!=belong[v]){
in[belong[v]]++;
}
}
for(int i=;i<=ans;i++){
if(!in[i])cnt++;
}
printf("%d",cnt);
}
【总结】
样例数据是万能的，不能过于相信样例，但是样例错了那就肯定错了
(另外，之前看见有人说原本想并查集但是错了，我个人没有想通为何不能简单的用并查集来偷懒，希望大佬能指点我一番)