76pts求助(悬2关)
查看原帖
76pts求助(悬2关)
1287433
__ycy1124__楼主2024/9/29 20:21
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>a[10001];
int idx=0,dfn[10001],low[10001],Color=0;
bool bj[10001];
int n,m,color[10001];
stack<int>q;
int w[10001];
void dfs(int p){
	bj[p]=1;
	dfn[p]=low[p]=++idx;
	q.push(p);
	for(auto it:a[p]){
		if(!dfn[it]){
			dfs(it);
			low[p]=min(low[p],low[it]);
		}
		else{
			if(bj[it]){
				low[p]=min(low[p],dfn[it]);
			}
		}
	}
	if(dfn[p]==low[p]){
		Color++;
		while(q.top()!=p){
			bj[q.top()]=0;
//			printf("%d %d\n",q.top(),Color);
			color[q.top()]=Color;
			q.pop();
		}
//		printf("%d %d\n",p,Color);
		bj[p]=0;
		q.pop();
		color[p]=Color;
	}
}
void tanjan(){
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i);
		}
	}
}
int ww[10001];
vector<int>t[10001];
int rd[10001];
int ans[10001];
bool vis[10001];
void Dfs(int p,int www){
	vis[p]=1;
	ans[p]=max(ans[p],www);
	for(auto it:t[p]){
		if(!vis[it]){
			Dfs(it,www+ww[it]);
		}
	}
	vis[p]=0;
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		w[i]=1;
	}
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
	}
	tanjan();
	for(int i=1;i<=Color;i++){
		for(int j=1;j<=n;j++){
			if(color[j]==i){
				ww[i]+=w[j];
				for(auto it:a[j]){
					if(color[it]==i){
						continue;
					}
					t[i].push_back(color[it]);
					rd[color[it]]++;
				}
			}
		}
	}
	for(int i=1;i<=Color;i++){
//		if(rd[i]==0){
			Dfs(i,ww[i]);
//		}
	}
	int wwww=0;
	for(int i=1;i<=Color;i++){
		if(ans[i]>=n){
			wwww+=ww[i];
		}
	}
	printf("%lld",wwww);
	return 0;
}
2024/9/29 20:21
加载中...