题目
题意
给出多组数据，每组数据有一个n和m，表示点数和边数。
之后m行，有两个数x和y，表示有一条从x到y的边（有环）
求至少要从多少点出发，可以遍历全图
思路
这题就是用Tarjan缩点，使图变为一个DAG，再找入度为0的点有几个就可以了。
如果不会Tarjan就别看了，还有注意是多组数据，要初始化。
这题就是这样，希望不要出现恶意评分！！！
代码
话不多说，给出代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
const int maxn=200001;
struct node{
int next,to;
}edge[maxn];//前向星建边
int n,m,dfn[maxn],tot,low[maxn],co[maxn],coc,cnt,in[maxn],head[maxn];
stack<int>sta;//这也可以手打，不过我懒
void Tarjan(int x){
dfn[x]=low[x]=++tot;sta.push(x);
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);
else if(!co[y]) low[x]=min(low[x],dfn[y]);//注意这里是dfn[y],不是low[y]!!
}
if(dfn[x]==low[x]){
co[x]=++coc;//找到一个环了，给点染色
while(sta.top()!=x)//同一个环的点染色
co[sta.top()]=coc,sta.pop();
sta.pop();//不要忘记这个，我经常错
}
}
int main(){
int tt;
scanf("%d",&tt);
while(tt--){
cnt=0,coc=0,tot=0;//一大堆初始化
memset(in,0,sizeof(in));//一大堆初始化
memset(head,0,sizeof(head));//一大堆初始化
memset(dfn,0,sizeof(dfn));//一大堆初始化
memset(low,0,sizeof(low));//一大堆初始化
memset(co,0,sizeof(co));//一大堆初始化
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
edge[++cnt]=(node){head[x],y};
head[x]=cnt;//建边
}
for(int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);//进行Tarjan缩点
int ans=0;
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=edge[j].next)
if(co[i]!=co[edge[j].to]) in[co[edge[j].to]]++;
//如果两个点不是同一种颜色，就说明它们不在同一环中，改变入度
for(int i=1;i<=coc;i++)
if(!in[i]) ans++;//这里是从coc个缩点中找入度为0的点
printf("%d\n",ans);
}
return 0;
}
希望能过，再%一下Venus大佬。
谢谢观看。