C/C++,图算法——求强联通的Tarjan算法之源程序

1 文本格式

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxk = 5005;

int n, k;
int id[maxn][5];
char s[maxn][5][5], ans[maxk];
bool vis[maxn];

struct Edge {
  int v, nxt;
} e[maxn * 100];

int head[maxn], tot = 1;

void addedge(int u, int v) {
  e[tot].v = v;
  e[tot].nxt = head[u];
  head[u] = tot++;
}

int dfn[maxn], low[maxn], color[maxn], stk[maxn], ins[maxn], top, dfs_clock, c;

void tarjan(int x) {  // tarjan算法求强联通
  stk[++top] = x;
  ins[x] = 1;
  dfn[x] = low[x] = ++dfs_clock;
  for (int i = head[x]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (!dfn[v]) {
      tarjan(v);
      low[x] = min(low[x], low[v]);
    } else if (ins[v])
      low[x] = min(low[x], dfn[v]);
  }
  if (dfn[x] == low[x]) {
    c++;
    do {
      color[stk[top]] = c;
      ins[stk[top]] = 0;
    } while (stk[top--] != x);
  }
}

int main() {
  scanf("%d %d", &k, &n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 3; j++) scanf("%d%s", &id[i][j], s[i][j]);

    for (int j = 1; j <= 3; j++) {
      for (int k = 1; k <= 3; k++) {
        if (j == k) continue;
        int u = 2 * id[i][j] - (s[i][j][0] == 'B');
        int v = 2 * id[i][k] - (s[i][k][0] == 'R');
        addedge(u, v);
      }
    }
  }

  for (int i = 1; i <= 2 * k; i++)
    if (!dfn[i]) tarjan(i);

  for (int i = 1; i <= 2 * k; i += 2)
    if (color[i] == color[i + 1]) {
      puts("-1");
      return 0;
    }

  for (int i = 1; i <= 2 * k; i += 2) {
    int f1 = color[i], f2 = color[i + 1];
    if (vis[f1]) {
      ans[(i + 1) >> 1] = 'R';
      continue;
    }
    if (vis[f2]) {
      ans[(i + 1) >> 1] = 'B';
      continue;
    }
    if (f1 < f2) {
      vis[f1] = 1;
      ans[(i + 1) >> 1] = 'R';
    } else {
      vis[f2] = 1;
      ans[(i + 1) >> 1] = 'B';
    }
  }
  ans[k + 1] = 0;
  printf("%s\n", ans + 1);
  return 0;
}
 

2 代码格式

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxk = 5005;int n, k;
int id[maxn][5];
char s[maxn][5][5], ans[maxk];
bool vis[maxn];struct Edge {int v, nxt;
} e[maxn * 100];int head[maxn], tot = 1;void addedge(int u, int v) {e[tot].v = v;e[tot].nxt = head[u];head[u] = tot++;
}int dfn[maxn], low[maxn], color[maxn], stk[maxn], ins[maxn], top, dfs_clock, c;void tarjan(int x) {  // tarjan算法求强联通stk[++top] = x;ins[x] = 1;dfn[x] = low[x] = ++dfs_clock;for (int i = head[x]; i; i = e[i].nxt) {int v = e[i].v;if (!dfn[v]) {tarjan(v);low[x] = min(low[x], low[v]);} else if (ins[v])low[x] = min(low[x], dfn[v]);}if (dfn[x] == low[x]) {c++;do {color[stk[top]] = c;ins[stk[top]] = 0;} while (stk[top--] != x);}
}int main() {scanf("%d %d", &k, &n);for (int i = 1; i <= n; i++) {for (int j = 1; j <= 3; j++) scanf("%d%s", &id[i][j], s[i][j]);for (int j = 1; j <= 3; j++) {for (int k = 1; k <= 3; k++) {if (j == k) continue;int u = 2 * id[i][j] - (s[i][j][0] == 'B');int v = 2 * id[i][k] - (s[i][k][0] == 'R');addedge(u, v);}}}for (int i = 1; i <= 2 * k; i++)if (!dfn[i]) tarjan(i);for (int i = 1; i <= 2 * k; i += 2)if (color[i] == color[i + 1]) {puts("-1");return 0;}for (int i = 1; i <= 2 * k; i += 2) {int f1 = color[i], f2 = color[i + 1];if (vis[f1]) {ans[(i + 1) >> 1] = 'R';continue;}if (vis[f2]) {ans[(i + 1) >> 1] = 'B';continue;}if (f1 < f2) {vis[f1] = 1;ans[(i + 1) >> 1] = 'R';} else {vis[f2] = 1;ans[(i + 1) >> 1] = 'B';}}ans[k + 1] = 0;printf("%s\n", ans + 1);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/210607.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vellum —— 相关特点

目录 Cloth Breaking and tearing Paneling and draping Cloth simulation Calculating mass and thickness Working with low res and high res cloth Quick moving cloth Softbody Vellum softbodies Plasticity with softbodies Constraints Stitch and slid…

Centos7 制作Openssh9.5 RPM包

Centos7 制作Openssh9.5 RPM包 最近都在升级Openssh版本到9.3.在博客里也放了openssh 9.5的rpm包. 详见:https://blog.csdn.net/qq_29974229/article/details/133878576 但还是有小伙伴不停追问这个rpm包是怎么做的,怕下载别人的rpm包里被加了盐. 于是做了个关于怎么用官方的o…

yolov8添加ca注意力机制

创建文件 coordAtt.py 位置&#xff1a;ultralytics/nn/modules/coordAtt.py ###################### CoordAtt #### start by AI&CV ############################### # https://zhuanlan.zhihu.com/p/655475515 import torch import torch.nn as nn import t…

2023年【A特种设备相关管理(锅炉压力容器压力管道)】考试内容及A特种设备相关管理(锅炉压力容器压力管道)复审考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 A特种设备相关管理&#xff08;锅炉压力容器压力管道&#xff09;考试内容根据新A特种设备相关管理&#xff08;锅炉压力容器压力管道&#xff09;考试大纲要求&#xff0c;安全生产模拟考试一点通将A特种设备相关管理…

使用 async/await 是必须避免的陷阱

使用 async/await 是必须避免的陷阱 如果我们使用过 nodejs&#xff0c;那么我们可能已经在 javaSoript 中使用了异步操作。异步任务是一个独立于 JavaSoript 引擎的主线程执行的操作。从本质上讲&#xff0c;这就是应用程序功能没有阻塞的 UI 的原因。 nodejs 的单线程性质&a…

外包干了2个月,技术明显退步了...

先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入广州某软件公司&#xff0c;干了接近5年的功能测试&#xff0c;今年11月份&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测…

kubectl获取命名空间下所有configmap集合的方法

前言&#xff1a; 获取单个configmap并忽略特定字段的操作可参照&#xff1a;kubectl获取ConfigMap导出YAML时如何忽略某些字段。 要获取命名空间下所有ConfigMap并忽略特定字段&#xff0c;你可以使用kubectl命令与例如yq这样的工具结合使用来忽略或删除不需要的字段。以下是…

MYSQL8用户权限配置详解

单位的系统性能问题需要把Mysql5升级到Mysql8&#xff0c;需要用到Mysql8的一些特性来提升系统的性能。 配置用户权限过程中发现一些问题&#xff0c;学习并记录一下。 目录 一、环境 二、MySQL8 用户权限 2.1 账号管理权限 2.1.1 连接数据库 2.1.2 账号权限配置 2.2 密码…

深信服AD负载均衡频繁掉线故障分析

一个由114.114.114.114引起的AD异常 客户反馈深信服负载均衡链路频繁掉线&#xff0c;具体故障现象如下 可以获取到IP地址、网关 两分钟掉一次&#xff0c;持续一个多月&#xff0c;求IT的心理阴影面积&#xff01; 链路监视器只设置了一个114.114.114.114 处理流程&#xff…

15:00的面试,15:06就出来了,问的问题过于变态了。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到5月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…

Web漏洞分析-SQL注入XXE注入(中下)

随着互联网的不断普及和Web应用的广泛应用&#xff0c;网络安全问题愈发引起广泛关注。在网络安全领域中&#xff0c;SQL注入和XXE注入是两个备受关注的话题&#xff0c;也是导致许多安全漏洞的主要原因之一。本博客将深入研究这两种常见的Web漏洞&#xff0c;带您探寻背后的原…

【数据结构】链表OJ题(顺序表)(C语言实现)

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ &#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1f33f;&#x1…

Linux Spug自动化运维平台本地部署与公网远程访问

文章目录 前言1. Docker安装Spug2 . 本地访问测试3. Linux 安装cpolar4. 配置Spug公网访问地址5. 公网远程访问Spug管理界面6. 固定Spug公网地址 前言 Spug 面向中小型企业设计的轻量级无 Agent 的自动化运维平台&#xff0c;整合了主机管理、主机批量执行、主机在线终端、文件…

分享66个在线客服JS特效,总有一款适合您

分享66个在线客服JS特效&#xff0c;总有一款适合您 66个在线客服JS特效下载 链接&#xff1a;https://pan.baidu.com/s/1VqM6ASgKRFdQ8RyzbsX4uA?pwd6666 提取码&#xff1a;6666 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0…

CubieBoard5(1)——烧录Linux镜像并远程登录

前言 最近项目使用CubieBoard5&#xff0c;但是网络资料甚少&#xff0c;官方文档资料放置得很零散。因此写下博客当做笔记。 准备 硬件 CubieBoard5开发板Windows PC配套电源线以及5V适配器Micro SD卡与读卡器网线 软件 XSHELL镜像文件烧录工具 烧录固件 从CubieBoard的…

【Unity动画】为一个动画片段添加事件Events

动画不管播放到那一帧&#xff0c;我们都可以在这里“埋伏”一个事件&#xff08;调用一个函数并且给函数传递一个参数&#xff0c;参数在外部设置&#xff0c;甚至传递一个物体&#xff09;&#xff01; 嗨&#xff0c;亲爱的Unity小伙伴们&#xff01;你是否曾想过为你的动画…

作业12.5

1.定义一个基类 Animal&#xff0c;其中有一个虛函数perform&#xff08;)&#xff0c;用于在子类中实现不同的表演行为。 #include <iostream>using namespace std; class Animal { private:int weight; public:Animal(){}Animal(int weight):weight(weight){}virtual …

【MVP矩阵】裁剪空间、NDC空间、屏幕空间

裁剪空间概述 裁剪空间是一个顶点乘以MVP矩阵之后所在的空间&#xff0c;Vertex Shader的输出就是在裁剪空间上&#xff08;划重点&#xff09; NDC空间概述 接上面&#xff0c;由GPU自己做透视除法将顶点转到NDC空间 两者的转换 透视除法将Clip Space顶点的4个分量都除以…

C语言学习笔记之数组篇

数组是一组相同类型元素的集合。 目录 一维数组 数组的创建 数组的初始化 数组的使用 数组在内存中的存储 二维数组 数组的创建 数组的初始化 数组的使用 数组在内存中的存储 数组名 数组名作函数参数 一维数组 数组的创建 type_t arr_name [const_n]; //type_…

51单片机制作数字频率计

文章目录 简介设计思路工作原理Proteus软件仿真软件程序实验现象测量误差和范围总结 简介 数字频率计是能实现对周期性变化信号频率测量的仪器。传统的频率计通常是用很多的逻辑电路和时序电路来实现的&#xff0c;这种电路一般运行较慢&#xff0c;而且测量频率的范围较小。这…