/*
     易得出状态转移为val[v] = max(val[v],val[pre] + a[v]) 
     于是通过tarjan算法把所有环缩为一点,跑一遍DAG上的DP即可 
*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10e5+5;

int scc[maxn],dfn[maxn],low[maxn],stac[maxn];
int a[maxn],head1[maxn],head2[maxn],vis[maxn];
int val[maxn],cnt,cnt1,scc_clock,top,n,m,tot,scc_amount;

struct node{
    int to,from,pre;
}g1[maxn*2],g2[maxn*2];//g1为原来的图，g2为缩点后的图 

void add1(int from,int to){
    g1[++cnt].from = from;
    g1[cnt].to = to;
    g1[cnt].pre = head1[from];
    head1[from] = cnt;
} //对应g1的add操作 

void add2(int from,int to){
    g2[++cnt1].from = from;
    g2[cnt1].to = to;
    g2[cnt1].pre = head2[from];
    head2[from] = cnt1;
} //对应g2的add操作 

void tarjan(int x){
    low[x] = dfn[x] = ++scc_clock;//初始化为时间戳 
    stac[++top] = x;vis[x] = 1;//入栈、标志数组设为1 
    for(register int i = head1[x];i;i = g1[i].pre){//遍历与x连接的点 
        int v = g1[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[x] = min(low[x],low[v]);
        }else if(vis[v]){
            low[x] = min(low[x],dfn[v]);
        }
    }//一顿tarjan的操作 
    if(low[x] == dfn[x]){
        scc_amount++;
        int y;
        while(y = stac[top--]){//出栈 
            scc[y] = x;
            vis[y] = 0;//我也不知道为啥 
            if(x == y) break;
            a[x] += a[y];//加权值 
        }
    }
}

int dfs(int u){
    val[u] = a[u];
    for(int i = head2[u];i;i = g2[i].pre){
        int v = g2[i].to;
        dfs(v);
        val[v] = max(val[v],val[u] + a[v]);
    }
}

int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;i++){
        scanf("%d",a+i);
    }
    for(register int i = 1;i <= m;i++){
        scanf("%d%d",&x,&y);
        add1(x,y);
    }
    for(register int i = 1;i <= n;i++){
        if(!dfn[i]) tarjan(i);//tarjan算法基本操作 
    }
    for(register int i = 1;i <= m;i++){
        x = scc[g1[i].from],y = scc[g1[i].to];
        if(x != y){//如果不属于同一强连通分量，就连边 
            add2(x,y);
        }
    }
    int ans = 0;
    for(int i = 1;i <= scc_amount;i++){
        if(!val[i]){
            dfs(i);
            ans = max(ans,val[i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

/*
无向图割点
对该图进行一次 Tarjan 算法（这里注意在搜索树中把无向边当做有向边看。即LOW[u]=min(LOW[u],DFN[v])(v 是 u 的祖先)的条件变为(v 是 u 的祖先且 v 不是 u 的父亲)）这样之后枚举搜索树上的所有边(u,v)，若存在 LOW[v]>=DNF[u]，则 u 是割点。
无向图割边
对该图进行一次 Tarjan 算法（这里注意在搜索树中把无向边当做有向边看。即LOW[u]=min(LOW[u],DFN[v])(v 是 u 的祖先)的条件变为(v 是 u 的祖先且 v 不是 u 的父亲)）这样之后枚举搜索树上的所有边(u,v)，若存在 LOW[v]>DNF[u]，则(u,v)为割边。
*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int low[maxn],dfn[maxn],cut[maxn];
int n,m,cnt;
vector<int> G[maxn];

void tarjan(int x,int father){
    int child = 0;
    low[x] = dfn[x] = ++cnt;
    for(int i = 0;i < G[x].size();i++){
        int v = G[x][i];
        if(!dfn[v]){
            tarjan(v,father);
            low[x] = min(low[x],low[v]);
            if(dfn[x] <= low[v] && x != father) cut[x] = 1;
            if(x == father) child++;
        }
        low[x] = min(low[x],dfn[v]);
    }
    if(x == father && child >= 2) cut[x] = 1;
}

int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i,i);
    for(int i = 1;i <= n;i++){
        if(cut[i]) ans++;
    }
    printf("%d\n",ans);
    for(int i = 1;i <= n;i++){
        if(cut[i]) printf("%d ",i);
    }
    return 0;
}

求割点

6.树上差分

7.拓扑排序

优质内容筛选与推荐>>
1、Windeln 优惠码 打折
2、虚函数、纯虚函数、抽象类、接口 （Java_C++_C#）
3、Yii之url路由管理
4、2016HUAS_ACM暑假集训4B - 递推
5、Bash游戏(博弈)

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

好看

已推荐到看一看

你的朋友可以在“发现”-“看一看”看到你认为好看的文章。

取消 推荐

我知道了

已取消，“好看”想法已同步删除

知道了