#2 RE
查看原帖
#2 RE
222250
LF_Forever楼主2024/8/31 15:20

在洛谷上#2RE,但是在本地没有问题,是怎么回事

#include<bits/stdc++.h>
#define M 200100
using namespace std;
int read(){
    int w = 1, s = 0;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') w = -w;
        ch = getchar();
    }
    while(isdigit(ch)){
        s = (s << 3) + (s << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w * s;
}
int n, m, f[M], cnt, c[M], siz[M];
vector<int>son[M];
queue<int>que;
int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
void deal(int x, int y){
    x = find(x), y = find(y);
    if(siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y];
    f[y] = x;
    for(int i : son[y]) son[x].push_back(i);
    if(siz[x] > 1) que.push(x);
}
int main(){
    // freopen("P6279_2.in", "r", stdin);
    // freopen("E.out", "w", stdout);
    n = read(), m = read();
    while(m --){
        int u = read(), v = read();
        son[u].push_back(v);
    }
    for(int i = 1; i <= n; ++ i){
        f[i] = i;
        if(son[i].size() > 1) que.push(i);
        siz[i] = son[i].size();
    }
    while(!que.empty()){
        int t = que.front(), tp = son[t][0]; que.pop();
        for(int i : son[t]){
            if(find(i) != find(tp)){
                deal(i, tp);
            }
        }
    }
    for(int i = 1; i <= n; ++ i){
        c[i] = c[find(i)];
        if(!c[i])
            c[find(i)] = c[i] = ++ cnt;
        printf("%d\n", c[i]);
    }
    return 0;
}

2024/8/31 15:20
加载中...