新做法

complexer · 2023-08-24 11:03:37 · 个人记录

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct edge{
    int v, w;
};
edge num[100010];

bool vis[100010];
int q[100010], b = 0, col[100010];
vector<int> r[100010], t[100010];

void dfs(int z){
    vis[z] = true;
    for(auto e: r[z])
        if(!vis[e])
            dfs(e);
    b++;
    num[z].v = b;
    num[z].w = z;
}

void dfs1(int z, int c){
    col[z] = c;
    vis[z] = true;
    for(auto e:r[z])
        if(!vis[e])
            dfs1(e, c);
}

bool cmp(edge x, edge y){
    return x.v > y.v;
}

signed main()
{
    int n, m, ans = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int o, p;
        cin >> o >> p;
        r[o].push_back(p);
        t[p].push_back(o);
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]) dfs(i);
    }
    sort(num + 1, num + n + 1, cmp);
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++){
        //cout << num[i].w << ' ';
        if(!vis[num[i].w]){
            ans++;
            dfs1(num[i].w, ans);
        }
    }
    //sort(col + 1, col + n + 1);
    //for(int i = 1; i <= n; i++) if(col[i] != col[i - 1] && col[i] != col[i + 1]) ans--;
    cout << ans;
    return 0;
}