跨服

思路：kosaraju缩点，判断缩点后的图是否有出度为0的点，我写的kosaraju的来源

代码：

#include<iostream>
#include<vector>
using namespace std;
struct Edge {
	int to, nextEdge;
};
struct Node {
	int cowSum;
	int out;//出度
};
vector<Node>node_s;
vector<Edge>edge;
vector<Edge>edgeBeside;
vector<int>head;
vector<int>headBeside;
vector<bool>visited;
vector<int>mappingNode;
int N, M;
void AddEdge(int from, int to,
             vector<Edge>&eg,
             vector<int>&hd) {
	Edge add = {to, hd[from]};
	hd[from] = eg.size();
	eg.push_back(add);
}
void DFS(int node, vector<int>&rememberNode,
         const vector<Edge>&eg,
         const vector<int>&hd) {
	visited[node]=1;
	rememberNode.push_back(node);
	for(int i=hd[node];i;i=eg[i].nextEdge){
		if(!visited[eg[i].to]){
			DFS(eg[i].to,rememberNode,eg,hd);
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	mappingNode.assign(N+1,0);
	edge.push_back({0, 0});
	edgeBeside.push_back({0, 0});
	head.assign(N + 1, 0);
	headBeside.assign(N + 1, 0);
	visited.assign(N + 1, 0);
	for (int i = 1; i <= M; i++) {
		int from, to;
		cin >> from >> to;
		AddEdge(from, to, edge, head);
		AddEdge(to, from, edgeBeside, headBeside);
	}
	vector<int>rememberNode;
	rememberNode.clear();
	for(int i=1;i<=N;i++){
		vector<int>add;
		add.clear();
		if(!visited[i]){
			DFS(i,add,edge,head);
		}
		for(int j=add.size()-1;j>=0;j--){
			rememberNode.push_back(add[j]);
		}
	}
	visited.assign(N+1,0);
	for(int i=N-1;i>=0;i--){
		vector<int>node_node;
		node_node.clear();
		if(!visited[rememberNode[i]]){
			DFS(rememberNode[i],node_node,edgeBeside,headBeside);
		}else{
			continue;
		}
		for(const int &node:node_node){
			mappingNode[node]=node_s.size();
		}
		node_s.push_back({int(node_node.size()),0});
	}
	for(int i=1;i<=N;i++){
		for(int j=head[i];j;j=edge[j].nextEdge){
			if(mappingNode[i]!=mappingNode[edge[j].to]){
				node_s[mappingNode[i]].out++;
			}
		}
	}
	int Ans=0;
	for(int i=1,length=node_s.size();i<length;i++){
		if(node_s[i].out==0&&Ans!=0){
			cout<<"0";
			return 0;
		}//*/
		if(node_s[i].out==0&&Ans==0){
			Ans=node_s[i].cowSum;
		}
	}
	cout<<Ans;
	return 0;
}