CSP 常用模板整理

$1.$ 并查集 $O(n\log\ n)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=10005;

int n,m,fa[N];

inline int find(int x) {
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

int main() {
    n=read();
    m=read();
    For(i,1,n) fa[i]=i; 
    For(q,1,m) {
        int op,x,y;
        op=read(),x=read(),y=read();
        if(op==1) fa[find(x)]=find(y);
        else puts((find(x)==find(y))?"Y":"N");
    }
    return 0;
}

$2.$ 堆 $O(n\log\ n)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int> qq;//大根堆

int main() {
    int n=read();
    while(n--) {
        int op,x;
        op=read();
        if(op==1) q.push(read());
        if(op==2) wln(q.top());
        if(op==3) q.pop();
    }
}

$3.$ 最小生成树(Kruskal) $O(m\log\ n)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define int long long
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=1e5+5;

int n,m,fa[N],ans,cnt;

struct node {
    int x,y,w;
    inline bool friend operator < (const node &a,const node &b) {
        return a.w<b.w;
    }
};
node a[N];

inline int find(int x) {
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

inline void Kruskal() {
    sort(a+1,a+cnt+1);
    int now=0;
    For(i,1,m) {
        int u=find(a[i].x);
        int v=find(a[i].y);
        if(u!=v) {
            now++;
            fa[u]=v;
            ans+=a[i].w;
        }
        if(now==n-1) break;
    }
}

signed main() {
    n=read(),m=read();
    For(i,1,n) fa[i]=i;
    For(i,1,m) {
        int u=read();
        int v=read();
        int w=read();
        a[++cnt]=(node){u,v,w};
    }
    Kruskal();
    wln(ans);
    return 0;
}

$4.$ 线性筛素数 $O(sqrt(n))$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=2e7+5;

int n,m,tot;

inline bool pd(int x) {
    if(x==1) return false;
    if(x==2) return true;
    for ( int i=2;i*i<=x;i++ ) 
        if(x%i==0) return false;
    return true;
}

int main() {
    n=read();
    m=read();
    while(m--) {
        int x=read();
        (pd(x))?puts("Yes"):puts("No");
    }
}

$5.$ 树状数组（单点加，区间改） $O(Q \log\ n)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define int long long
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=500005;

int n,m,c[N],a[N];

inline void add(int x,int val) {
    while(x<=n) {
        c[x]+=val;
        x+=lowbit(x);
    }
}

inline int query(int x) {
    int ret=0;
    while(x) {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

signed main() {
    n=read();
    m=read();
    For(i,1,n) add(i,read());
    for(;m--;) {
        int op,x,y;
        op=read();
        if(op==1) {
            x=read();
            y=read();
            add(x,y);
        }
        else {
            x=read();
            y=read();
            wln(query(y)-query(x-1));
        }
    }
    return 0;
}

$6.$ 树状数组（区间加单点查） $O(Q \log\ n)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define int long long
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=500005;

int n,m,c[N],a[N];

inline void add(int x,int val) {
    while(x<=n) {
        c[x]+=val;
        x+=lowbit(x);
    }
}

inline int query(int x) {
    int ret=0;
    while(x) {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

signed main() {
    n=read();
    m=read();
    int las=0,x;
    For(i,1,n) {
        add(i,(x=read())-las);
        las=x;
    }
    for(;m--;) {
        int op,x,y,v;
        op=read();
        if(op==1) {
            x=read();
            y=read();
            v=read();
            add(x,v);
            add(y+1,-v);
        }
        else {
            y=read();
            wln(query(y));
        }
    }
    return 0;
}

$7.$ 线段树（区间加区间查） $O(Q \ log\ n)*$ 大常数

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define db double
#define int long long
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=100005;
const int M=N<<2;

int n,m,tr[M],add[M],a[N],ans;

inline void build(int rt,int l,int r) {
    if(l==r) {
        tr[rt]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}

inline void pushdown(int rt,int l,int r) {
    if(add[rt]) {
        int mid=(l+r)/2;
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        tr[rt<<1]+=add[rt]*(mid-l+1);
        tr[rt<<1|1]+=add[rt]*(r-mid);
        add[rt]=0;
    }
}

inline void modify(int rt,int l,int r,int ll,int rr,int val) {
    if(ll<=l&&r<=rr) {
        tr[rt]+=val*(r-l+1);
        add[rt]+=val;
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)/2;
    if(ll<=mid) modify(rt<<1,l,mid,ll,rr,val);
    if(rr>mid) modify(rt<<1|1,mid+1,r,ll,rr,val);
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}

inline int query(int rt,int l,int r,int ll,int rr) {
    if(ll<=l&&r<=rr) return tr[rt];
    int mid=(l+r)/2,ret=0;
    pushdown(rt,l,r);
    if(ll<=mid) ret=(ret+query(rt<<1,l,mid,ll,rr));
    if(rr>mid) ret=(ret+query(rt<<1|1,mid+1,r,ll,rr));
    return ret;
}

signed main() {
    n=read();
    m=read();
    For(i,1,n) a[i]=read();
    build(1,1,n);
    for(;m--;) {
        int op,x,y,k;
        op=read();
        if(op==1) {
            x=read();
            y=read();
            k=read();
            modify(1,1,n,x,y,k);
        }
        else {
            x=read();
            y=read();    
            wln(query(1,1,n,x,y));
        }
    }
}

$8.$ 倍增LCA $O(n \log\ n)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
//#define int long long
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=500005;

int n,m,head[N],dep[N],f[N][22],cnt;

struct nood {
    int nex,to;
};
nood e[N<<1];

inline void jia(int u,int v) {
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}

inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    For(i,1,21) f[u][i]=f[f[u][i-1]][i-1];
    FOR(i,u) {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
    }
}

inline int lca(int a,int b) {
    if(dep[a]>dep[b]) swap(a,b);
    Dow(i,20,0) 
        if(dep[b]-(1<<i)>=dep[a]) b=f[b][i];
    if(a==b) return a;
    Dow(i,20,0) 
        if(f[a][i]!=f[b][i]) {
            a=f[a][i];
            b=f[b][i];
        }
    return f[a][0];
}

int main() {
    n=read();
    m=read();
    int rt=read();
    For(i,1,n-1) {
        int u=read();
        int v=read();
        jia(u,v);
        jia(v,u);
    }
    dfs(rt,0);
    while(m--) {
        int x=read();
        int y=read();
        wln(lca(x,y));
    }
    return 0;
}

$8.$ spfa $O(n+m)$

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=e[i].nex )
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=10005;
const int M=500005;

int n,m,head[N],cnt,s;
int vis[N],dis[N];

struct nood { 
    int nex,to,w;
};
nood e[M<<1];

inline void jia(int u,int v,int w) {
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].w=w;
}

inline void spfa(int s) {
    queue<int>q;
    mem(vis,0);
    mem(dis,63);
    q.push(s),vis[s]=1,dis[s]=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        FOR(i,u) {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w) {
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}


int main() {
    n=read();
    m=read();
    s=read();
    For(i,1,m) {
        int u=read();
        int v=read();
        int w=read();
        jia(u,v,w);
        jia(v,u,w);
    }
    spfa(s);
    For(i,1,n) wrn((dis[i]>1e6)?2147483647:dis[i]);
    return 0;
}

$9.$ 树链剖分 $O(q \log\ n)$

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

const int maxn=4e5+5;
struct node 
{
    int nex,to;
} e[maxn];
int id[maxn],tr[maxn],tag[maxn],fa[maxn];
int n,m,cnt,type,ans,res,top[maxn],now,head[maxn];
int rt,mod,siz[maxn],dep[maxn],w[maxn],wt[maxn],son[maxn];

inline void add_edge(int u,int v) 
{
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}

inline void push_down(int rt,int len) 
{
    tag[rt<<1]+=tag[rt];
    tag[rt<<1|1]+=tag[rt];
    tr[rt<<1]+=tag[rt]*(len-(len>>1));
    tr[rt<<1|1]+=tag[rt]*(len>>1);
    tr[rt<<1]=tr[rt<<1]%mod;
    tr[rt<<1|1]=tr[rt<<1|1]%mod;
    tag[rt]=0;
}

inline void build(int rt,int l,int r) 
{
    if(l==r) 
    {
        tr[rt]=wt[l];
        if(tr[rt]>mod) tr[rt]%=mod;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tr[rt]=(tr[rt<<1]+tr[rt<<1|1])%mod;
}

inline void query(int rt,int l,int r,int L,int R) 
{
    if(L<=l and r<=R) 
    {
        res=res+tr[rt];
        res%=mod;
        return;
    }
    else 
    {
        int mid=(l+r)>>1;
        if(tag[rt]) push_down(rt,r-l+1);
        if(L<=mid) query(rt<<1,l,mid,L,R);
        if(mid<R) query(rt<<1|1,mid+1,r,L,R);
    }
}

inline void modify(int rt,int l,int r,int L,int R,int z) 
{
    if(L<=l and R>=r) 
    {
        tag[rt]=tag[rt]+z;
        tr[rt]=tr[rt]+z*(r-l+1);
    }
    else 
    {
        int mid=(l+r)>>1;
        if(tag[rt]) push_down(rt,r-l+1);
        if(L<=mid) modify(rt<<1,l,mid,L,R,z);
        if(mid<R) modify(rt<<1|1,mid+1,r,L,R,z);
        tr[rt]=(tr[rt<<1]+tr[rt<<1|1])%mod;
    }
}

inline int qrange(int x,int y) 
{
    int ret=0;
    while(top[x]!=top[y]) 
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res=0;
        query(1,1,n,id[top[x]],id[x]);
        ret=ret+res;
        ret%=mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=0;
    query(1,1,n,id[x],id[y]);
    ret=ret+res;
    ret%=mod;
    return ret;
}

inline void updrange(int x,int y,int z) 
{
    z=z%mod;
    while(top[x]!=top[y]) 
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        modify(1,1,n,id[top[x]],id[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(1,1,n,id[x],id[y],z);
}

inline int qson(int x) 
{
    res=0;
    query(1,1,n,id[x],id[x]+siz[x]-1);
    return res;
}

inline void updson(int x,int z) 
{
    modify(1,1,n,id[x],id[x]+siz[x]-1,z);
}

inline void dfs1(int x,int f,int deep) 
{
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for ( re int i=head[x];i;i=e[i].nex ) 
    {
        int v=e[i].to;
        if(v==f) continue;
        dfs1(v,x,deep+1);
        siz[x]=siz[x]+siz[v];
        if(siz[v]>maxson) 
        {
            son[x]=v;
            maxson=siz[v];
        }
    }
}

inline void dfs2(int x,int topf) 
{
    id[x]=++now;
    wt[now]=w[x];
    top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x],topf);
    for ( re int i=head[x];i;i=e[i].nex ) 
    {
        int v=e[i].to;
        if(v==fa[x] or v==son[x]) continue;
        dfs2(v,v);
    }
}

inline int read() 
{
    int z=0,f=1;char k;
    while(k<'0'||k>'9'){if(k=='-')f=-1;k=getchar();}
    while(k>='0'&&k<='9'){z=(z<<3)+(z<<1)+k-'0';k=getchar();}
    return z*f;
}

signed main() {
    n=read(),m=read(),rt=read(),mod=read();
    for ( re int i=1;i<=n;i++ ) w[i]=read();
    for ( re int i=1;i<=n-1;i++ )
    {
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(rt,0,1);
    dfs2(rt,rt);
    build(1,1,n);
    while(m--) 
    {
        type=read();
        if(type==1) 
        {
            int x=read(),y=read(),z=read();
            updrange(x,y,z);
        }
        else if(type==2) 
        {
                int x=read(),y=read();
                printf("%lld\n",qrange(x,y));
        }
        else if(type==3) 
        {
                int x=read(),y=read();
                updson(x,y);
        }
        else if(type==4) 
        {
                int x=read();
                printf("%lld\n",qson(x));
        }
    }
    return 0;
}

$10.$ tarjan缩点 $O(n+m)$

#include <bits/stdc++.h>
#define re register
using namespace std;
const int maxn=1e5+5,maxm=2e5+5;
struct node {
    int nex,to;
} e[maxm<<1];
int head[maxn],dfn[maxn],val[maxn];
int stak[maxn],low[maxn],col[maxn];
int rd[maxn],f[maxn],size[maxn],u[maxm],v[maxm];
int n,m,cnt,top,now,sum,res,ans;
inline void add_edge(int u,int v) {
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}
inline int read() {
    int sum=0,ff=1; char ch=getchar();
    while(ch<'0' or ch>'9') { if(ch=='-') ff=-1; ch=getchar(); }; 
    while(ch>='0' and ch<='9') { sum=sum*10+ch-'0'; ch=getchar(); }; 
    return sum*ff;
}
inline void tarjan(int u) {
    low[u]=dfn[u]=++now;
    stak[++top]=u;
    for ( re int i=head[u];i;i=e[i].nex ) {
        int v=e[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else 
            if(!col[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        col[u]=++sum;
        size[sum]=val[u];
        while(u!=stak[top]) {
            col[stak[top]]=sum;
            size[sum]+=val[stak[top]];
            top--;
        }
        top--;
    }
}
inline void dfs(int u) {
    if(f[u]) return;
    f[u]=size[u]; int tmp=0;
    for ( re int i=head[u];i;i=e[i].nex ) {
        int v=e[i].to;
        dfs(v);
        tmp=max(tmp,f[v]);
    }
    f[u]+=tmp;
}
int main() {
    memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn));
    n=read(),m=read();
    for ( re int i=1;i<=n;i++ ) val[i]=read();
    for ( re int i=1;i<=m;i++ ) {
        u[i]=read(),v[i]=read();
        add_edge(u[i],v[i]);
    }
    for ( re int i=1;i<=n;i++ ) if(!dfn[i]) tarjan(i);
    cnt=0; memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); cnt=0;
    for ( re int i=1;i<=m;i++ ) 
        if(col[u[i]]!=col[v[i]]) 
            add_edge(col[u[i]],col[v[i]]);
    for ( re int i=1;i<=sum;i++ ) {
        if(!f[i]) dfs(i);
        res=max(res,f[i]);
    }
    printf("%d\n",res);
    return 0;
}

$...$ 未完待续