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)
blank

相关推荐

  • Linux VI文本编辑器

    Linux VI文本编辑器VI文本编辑器  学会使用vi编辑器是学习Linux系统的必备技术之一,因为一般的Linux服务器是没有GUI界面的,Linux运维及开发人员基本上都是通过命令行的方式进行文本编辑或程序编写的。vi编辑器是Linux内置的文本编辑器,几乎所有的类unix系统中都内置了vi编辑器,而其它编辑器则不一定,另外很多软件会调用vi编辑进行内容编写,例如cront…

  • IE内存溢出报错Stack overflow at line[通俗易懂]

    IE内存溢出报错Stack overflow at line[通俗易懂]该错误只在IE中出现,出现该提示的原因主要有两种:1.重定义了系统的触发事件名称作为自定义函数名如: onclick/onsubmit… 都是系统保留的事件名称,不允许作为重定义函数名称。2.出现死循环,都提示:Stackoverflowatline:0,如:在图片对象定义了onerror事件的循环处理、onload这里并不是说/im

  • java基础入门(一)[通俗易懂]

    前言:1.笔者的java没有经过真正系统的学习过,只是跟着书上自学的。所以有些地方难免会理解错误之类的,如果看到错误的地方,请指出来,或者有什么不理解的地方也可以提出来,大家一起进步。2.这篇教程是一个学习方向的引导,且只针对基础入门(更加进阶的知识笔者也还在学习)。3.java的基础入门知识网上有很多,很多大神的博客里也有总结,笔者不认为自己能比大神总结的好。所以在这篇教程里,…

  • 差分数组详解[通俗易懂]

    差分数组详解[通俗易懂]题目:来先看一道裸题,有n个数。m个操作,每一次操作,将x~y区间的所有数增加z;最后有q个询问,每一次询问求出x~y的区间和。思路:很明显,直接用前缀和无法快速满足这个操作,所以我们就用到了查分数组。设a数组表示原始的数组;设d[i]=a[i]-a[i-1](1&lt;i≤n,d[1]=a[1]);设f[i]=f[i-1]+d[i](1&lt;i≤n,f[1]=d[1]=a[1]);设sum[i…

  • yablog: calculate cosine with python numpy

    yablog: calculate cosine with python numpy

  • Python快速编程入门课后习题答案「建议收藏」

    Python快速编程入门课后习题答案「建议收藏」文章目录前言第一章一、填空题二、判断题三、选择题四、简答题第二章一、填空题二、判断题三、选择题四、简答题第三章一、填空题二、判断题三、选择题四、简答题第四章一、单选题二、判断题三、填空题四、程序分析题第五章一、选择题二、判断题三、填空题四、简答题五、程序分析题第六章一、单选题二、判断题三、填空题四、简答题五、程序分析题第七章一、单选题二、判断题三、填空题四、简答题五、程序分析题第八章一、单选题二、…

发表回复

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

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