强连通分量

1.缩点成一个有向无环图

2.如果有没被遍历到的点就要输出-1

3.统计每个点的入度

4.入度为0的点的数量就是答案

50分代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num,k,cnt,ans;
int in[505],x[505],a[505],head[505];
int dfn[505],low[505],vis[505],tem[505];
stack<int>s;
struct Node{
	int to,next;
}edge[505*505];
void add(int u,int v){
	edge[++num].to=v;
	edge[num].next=head[u];
	head[u]=num;
}
void tarjan(int x){
	dfn[x]=low[x]=++cnt;
	s.push(x);
	vis[x]=1;
	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(vis[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]){
		k++;
		while(s.top()!=x){
			int q=s.top();
			vis[q]=0;
			tem[q]=cnt;
			s.pop();
		}
		tem[x]=cnt;
		s.pop();
		vis[x]=0;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x[i]; 
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<=a[i];j++){
			cin>>k;
			add(i,k);
		}
	}
	for(int i=1;i<=m;i++){
		if(!dfn[x[i]]){
			tarjan(x[i]);
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			cout<<"-1";
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=edge[j].next){
			int v=edge[j].to;
			if(tem[i]!=tem[v]){
				in[v]++;
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(!in[x[i]]){
			ans++;
		} 
	}
	cout<<ans;
	return 0;
}

100分代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num,k,cnt,ans;
int in[505],x[505],a[505],head[505];
int dfn[505],low[505],vis[505],tem[505];
stack<int>s;
vector<int>rul;
struct Node{
	int to,next;
}edge[505*505];
void add(int u,int v){
	edge[++num].to=v;
	edge[num].next=head[u];
	head[u]=num;
}
void tarjan(int x){
	dfn[x]=low[x]=++cnt;
	s.push(x);
	vis[x]=1;
	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(vis[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]){
		k++;
		while(s.top()!=x){
			int q=s.top();
			vis[q]=0;
			tem[q]=cnt;
			s.pop();
		}
		tem[x]=cnt;
		s.pop();
		vis[x]=0;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x[i]; 
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<=a[i];j++){
			cin>>k;
			add(i,k);
		}
	}
	for(int i=1;i<=m;i++){
		if(!dfn[x[i]]){
			rul.push_back(x[i]);
			tarjan(x[i]);
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			cout<<"-1";
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=edge[j].next){
			int v=edge[j].to;
			if(tem[i]!=tem[v]){
				in[v]++;
			}
		}
	}
	for(int i=0;i<rul.size();i++){
		if(!in[rul[i]]){
			ans++;
		} 
	}
	cout<<ans;
	return 0;
}

我们发现区别在于100分的代码,在最后没有判断能从一个点到达的点

有点绕,没关系,我们看个图

图中4号点为1,2,3号点的缩点

你会发现老大连的1号点入度为0,但是在新图中的入度却不是0

这就会导致答案错误

其实你也可以通过统计新图的入度来避免这种错误

end