当前位置: 首页 > news >正文

UVa11324 - The Largest Clique

Online Judge

题目大意:有一张n个点m条边的图,现对于每一个点u,建立一条边连接它和所有它能到达的点,问满足所有点之间都有边的分量的大小最大是多少

0<=n<=1000;0<=m<=50000

思路:根据建新图的规则可知,一个点会和它能到达的所有点构成一个合法的分量,那么从入度为0的点开始组成的这样一个分量一定是最大的,但是因为图中有环,所以没法直接统计这样的分量的大小,所以要先用tarjan将所有强量通分量缩成一个点,再在新图中用记忆化搜索找上述的分量

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int head[N], head2[N];
struct Edge
{int v, next;
}e[N * N], e2[N * N];
int dfn[N], low[N];
int c1 = 0, c2 = 0;
void addedge(int u, int v)
{//原图e[++c1].v = v;e[c1].next = head[u];head[u] = c1;
}
void addedge2(int u, int v)
{//缩点后的新图e2[++c2].v = v;e2[c2].next = head2[u];head2[u] = c2;
}
bool vis[N];
int cnt = 0;
int ans = 0;
stack<int>s;
int siz[N];
pair<int, int>edge[N * N];
int n, m;
int cnts[N];
int scc[N];
void tarjan(int u)
{//将图拆解成强连通分量的组合cnt++;//访问次序dfn[u] = low[u] = cnt;//每个点的访问次序,在第几个强连通分量里	s.push(u);//储存dfs中待处理的点vis[u] = 1;//在栈内待处理for (int i = head[u]; ~i; i=e[i].next){int v = e[i].v;if (!dfn[v]){//子节点没被访问过tarjan(v);low[u] = min(low[u], low[v]);//和子节点合并成一个强连通分量}else if (vis[v]){//重复访问了栈内的节点low[u] = min(low[u], low[v]);//这两个点一定在一个强连通分量内}}if (dfn[u] == low[u]){//当前点是这个强连通分量的第一个点,也就是这个分量都已处理完毕int temp = 0;//记录强连通分量的点数ans++;//第几个强连通分量while (!s.empty() && s.top() != u){//将这个强量通分量内的点全部弹出		vis[s.top()] = 0;//不在栈内scc[s.top()] = ans;//每个点属于哪个强连通分量temp++;s.pop();}temp++;vis[s.top()] = 0;//第一个点也要弹出scc[s.top()] = ans;s.pop();siz[ans] = temp;//这个连通块里面几个点}
}
int in[N];
void init()
{c1 = c2 = 0;for (int i = 1; i <= n; i++){vis[i] = 0;dfn[i] = low[i] = siz[i] = 0;head[i] = head2[i] = -1;cnts[i] = 0;in[i] = 0;}while (!s.empty()){s.pop();}cnt = ans = 0;
}
int dfs(int u)
{//记忆化搜索能到达多少个点if (cnts[u]){return cnts[u];}int ma = 0;for (int i = head2[u]; ~i; i=e2[i].next){int v = e2[i].v;ma = max(ma, dfs(v));//取子节点里面最大的}cnts[u] = siz[u] + ma;//这个歌两桶快的大小加子节点传来的值return cnts[u];
}
void solve()
{cin >> n >> m;init();for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;edge[i] = { u,v };addedge(u, v);}for (int i = 1; i <= n; i++){if (!dfn[i])//所有没处理的点都要处理tarjan(i);}for (int i = 1; i <= m; i++){int u = edge[i].first, v = edge[i].second;if (scc[u] != scc[v]){//两个点不在一个强连通分块里addedge2(scc[u], scc[v]);//建新图in[scc[v]]++;}}int out = 0;for (int i = 1; i <= n; i++){if (!in[i]){//从入度为0的点出发开始搜out = max(out, dfs(i));}}cout << out << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}

http://www.lryc.cn/news/183308.html

相关文章:

  • 【Linux】TCP的服务端(守护进程) + 客户端
  • 1.7. 找出数组的第 K 大和原理及C++实现
  • 基于微信小程序的付费自习室
  • 纪念在CSDN的2048天
  • 云原生Kubernetes:简化K8S应用部署工具Helm
  • qml保姆级教程五:视图组件
  • 2310d编译不过
  • CleanMyMac X4.14.1最新版本下载
  • 芯驰D9评测(3)--建立开发环境
  • 阿里云服务器IP地址查询方法(公网IP和私网IP)
  • 第47节——使用bindActionCreators封装actions模块
  • QT、c/c++通过宏自动判断平台
  • 对比表:阿里云轻量应用服务器和服务器性能差异
  • 中国1km分辨率月最低温和最高温度数据集(1901-2020)
  • EasyX图形库note4,动画及键盘交互
  • C++设计模式-原型(Prototype)
  • [补题记录] Atcoder Beginner Contest 322(E)
  • 目标检测算法改进系列之Backbone替换为FocalNet
  • buuctf-[BSidesCF 2020]Had a bad day 文件包含
  • Elasticsearch:什么时候应该考虑在 Elasticsearch 中添加协调节点?
  • Dubbo3应用开发—Dubbo注册中心引言
  • AS环境,版本问题,android开发布局知识
  • OpenCV查找和绘制轮廓:findContours和drawContours
  • 毕设-原创医疗预约挂号平台分享
  • PLL锁相环倍频原理
  • POJ 2886 Who Gets the Most Candies? 树状数组+二分
  • 阿里云服务器镜像系统Anolis OS龙蜥详细介绍
  • 数学建模Matlab之基础操作
  • [计算机入门] Windows附件程序介绍(工具类)
  • 队列(循环数组队列,用队列实现栈,用栈实现队列)