uva 11324 The Largest Clique(图论-tarjan,动态规划)

uva 11324 The Largest Clique(图论-tarjan,动态规划)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Problem B: The Largest Clique

uva 11324 The Largest Clique(图论-tarjan,动态规划)

Given a directed graph G, consider the following transformation. First, create a new graph T(G) to have the same vertex set as G. Create a directed edge between two vertices u and v in T(G) if and only if there is a path between u and v in G that follows the directed edges only in the forward direction. This graph T(G) is often called the transitive closure of G.

We define a clique in a directed graph as a set of vertices U such that for any two vertices u and v in U, there is a directed edge either from u to v or from v to u (or both). The size of a clique is the number of vertices in the clique.

The number of cases is given on the first line of input. Each test case describes a graph G. It begins with a line of two integers n and m, where 0 ≤ n ≤ 1000 is the number of vertices of G and 0 ≤ m ≤ 50,000 is the number of directed edges of G. The vertices of G are numbered from 1 to n. The following m lines contain two distinct integers u and v between 1 and n which define a directed edge from u to v in G.

For each test case, output a single integer that is the size of the largest clique in T(G).

Sample input

1
5 5
1 2
2 3
3 1
4 1
5 2

Output for sample input

4

Zachary Friggstad

题目大意:

T组測试数据。给一张有向图G。求一个结点数最大的结点集,使得该结点中随意两个结点 u 和 v满足:要么 u 能够到达 v。 要么 v 能够到达 u(u 和 v 相互可达也能够)。

解题思路:

”同一个强连通分量中的点要么都选,要么不选。把强连通分量收缩点后得到SCC图。让每一个SCC结点的权等于它的结点数,则题目转化为求SCC图上权最大的路径。因为SCC图是一个 DAG, 能够用动态规划求解。

解题代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=1100;
const int maxm=51000;

struct edge{
    int u,v,next;
    edge(int u0=0,int v0=0){
        u=u0;v=v0;
    }
}e[maxm];

int n,m,head[maxn],dfn[maxn],low[maxn],mark[maxn],w[maxn],color[maxn],dp[maxn],cnt,nc,index;
vector <int> vec;
vector <vector<int> > dfsmap;

void addedge(int u,int v){
    e[cnt]=edge(u,v);e[cnt].next=head[u];head[u]=cnt++;
}

void input(){
    cnt=nc=index=0;
    scanf("%d%d",&n,&m);
    vec.clear();
    for(int i=0;i<=n;i++){
        w[i]=dfn[i]=0;
        mark[i]=false;
        color[i]=dp[i]=head[i]=-1;
    }
    int u,v;
    while(m-- >0){
        scanf("%d%d",&u,&v);
        addedge(u,v);
    }
}

void tarjan(int s){
    dfn[s]=low[s]=++index;
    mark[s]=true;
    vec.push_back(s);
    for(int i=head[s];i!=-1;i=e[i].next){
        int d=e[i].v;
        if(!dfn[d]){
            tarjan(d);
            low[s]=min(low[d],low[s]);
        }else if(mark[d]){
            low[s]=min(low[s],dfn[d]);
        }
    }
    if(dfn[s]==low[s]){
        nc++;
        int d;
        do{
            d=vec.back();
            vec.pop_back();
            color[d]=nc;
            mark[d]=false;
            w[nc]++;
        }while(d!=s);
    }
}

int DP(int s){
    if(dp[s]!=-1) return dp[s];
    int ans=w[s];
    for(int i=0;i<dfsmap[s].size();i++){
        int d=dfsmap[s][i];
        if(DP(d)+w[s]>ans) ans=DP(d)+w[s];
    }
    return dp[s]=ans;
}

void solve(){
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    dfsmap.clear();
    dfsmap.resize(nc+1);
    for(int i=0;i<cnt;i++){
        int x=color[e[i].u],y=color[e[i].v];
        if(x!=y){
            dfsmap[x].push_back(y);
            //cout<<x<<"->"<<y<<endl;
        }
    }
    int ans=0;
    for(int i=1;i<=nc;i++){
        if(DP(i)>ans) ans=DP(i);
        //cout<<i<<" "<<ans<<endl;
    }
    printf("%d\n",ans);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t-- >0){
        input();
        solve();
    }
    return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116923.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c# splitContainer控件

    c# splitContainer控件splitContainer可以把窗口拆分为两部分可以使用多个splitContainer常用属性(1).splitContainer不能被鼠标直接点击选中,可通过右击->选择splitContainer选中。(2).属性IsSplitterFixed用于设置拆分器能否移动。(3).属性FixedPanel若设置为Panel1(或Panel2),在调整窗

  • TPshop学习(8)微信支付

    TPshop学习(8)微信支付

    2021年10月14日
  • 如何学习verilog,如何快速入门?

    前言害怕真的有人不知道verilog是什么东西,于是就给把百度给搬来了!VerilogHDL是一种硬件描述语言,以文本形式来描述数字系统硬件的结构和行为的语言,用它可以表示逻辑电路图、逻辑表达式,还可以表示数字逻辑系统所完成的逻辑功能。VerilogHDL和VHDL是世界上最流行的两种硬件描述语言,都是在20世纪80年代中期开发出来的。前者由GatewayDesignAutomation公司(该公司于1989年被Cadence公司收购)开发。两种HDL均为IEEE标准。之前的文章《IC前端

  • Google搜索语法_谷歌高级搜索怎么用

    Google搜索语法_谷歌高级搜索怎么用Google搜索技巧是利用各种高级搜索语法或者搜索指令,让我们能够使用谷歌进行精确化的搜索,外贸找客户和学术文件查找都可以应用到这些搜索技巧。搜索技巧#1:关键词精确查询使用谷歌搜索时,用英文引号把关键词框起来,Google会进行完全匹配的精确搜索,搜索结果中的页面会包含完整的关键词或者词组。搜索实例比如,我们想要查找谷歌站长工具相关的信息,不限定网页的类型,但必须包含“谷歌站长工具”这个完整的词汇。语法指令“谷歌站长工具”搜索结果搜索技巧#2:OR选择查询一般情况

  • pycharm2021.7.20激活码(注册激活)

    (pycharm2021.7.20激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlMLZPB5EL5Q-eyJsaWNlbnNlSW…

  • gridview样式模板_react-grid-layout

    gridview样式模板_react-grid-layoutGridView中有些td、th的样式不好设置或是里面的控件,可能用如下方式设置table.GridView td,th{    PADDING-RIGHT:1px;   PADDING-LEFT:3px;   PADDING-BOTTOM:1px;   PADDING-TOP:1px;   FONT-FAMILY:Arial,宋体,Verdan…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号