提出 #75245155

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e18
#define eps 1e-9
#define ls 2*k
#define rs 2*k+1
using namespace std;

const int N=3e5+5,M=1e7;
const int mod=998244353;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int n,q,d[N];
int f[N],siz[N];
bool vis[N];
inline void dfs(int x,int now){
	if(vis[x]) return ;
	vis[x]=1;
	now++;
	if(f[x]>n) siz[f[x]-n]=now;
	else dfs(f[x],now);
	return ;
}

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc=1; 
    while(tc--){
    	cin>>n>>q;
    	for(int i=1;i<=n;i++) f[i]=n+i;
    	while(q--){
    		int x,y;
    		cin>>x>>y;
    		if(f[x]<=n) d[f[x]]--;
    		f[x]=y;
    		d[y]++;
		}
		for(int i=1;i<=n;i++)
			if(!d[i]) dfs(i,0);
		for(int i=1;i<=n;i++) cout<<siz[i]<<' ';
    }

    return 0;
}

提出情報

ジャッジ結果