1个点超时,求优化,悬关
查看原帖
1个点超时,求优化,悬关
676429
z_w_b楼主2025/6/30 13:53
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define x first
#define y second
const int N=1e5+10;
const int INF=INT_MAX;
int n,m;
bool dist[N];
vector<int> g[N];
void dijkstra(int s){
    for(int i=0;i<=n;i++) dist[i]=0;
    dist[s]=1;
    queue<int> heap;
    heap.push(s);
    while (!heap.empty()){
        int u=heap.front();
        heap.pop();
        for(int v=0;v<g[u].size();v++){
            if(!dist[g[u][v]]){
                dist[g[u][v]]=1;
                heap.push(g[u][v]);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	g[i].push_back(i);
	}
    while (m--){
        int a,b;
        cin>>a>>b;
        g[b].push_back(a);
    }
    int c=1,ans=0;
    for(int i=1;i<=n;i++){
    	dijkstra(i);
    	for(int j=1;j<=n;j++){
    		if(!dist[j]){
    			c=0;
    			break;
			}
		}	
    	ans+=c;
    	c=1;
	}
	cout << ans;
    return 0;
}

2025/6/30 13:53
加载中...