AI 助理
备案控制台
开发者社区 云计算 文章 正文

tarjan求强连通分量

2024-01-10 120
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： tarjan求强连通分量

原理看:1

推导过程看:2

模板

/*********************************************************************
    程序名:
    版权:
    作者:
    日期: 2022-07-05 17:11
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
bool instack[N];
stack<int>s;
int timestamp;
int low[N];
int dfn[N];
int n, m;
vector<int>g[N];
int cnt;
int id[N];
void tarjan(int u)
{
  dfn[u] = low[u] = ++timestamp;
  s.push(u);
  instack[u] = true;
  for (auto j : g[u])
    {
      if (!dfn[j])
        {
          tarjan(j);
          low[u] = min(low[u], low[j]);
        }
      else if (instack[j])
        {
          low[u] = min(low[u], dfn[j]);
        }
    }
  if (dfn[u] == low[u])
    {
      int y;
      ++cnt;
      do
        {
          y = s.top();
          instack[y] = false;
          s.pop();
          id[y] = cnt;
        }
      while (u != y);
    }
  return;
}
void solve()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
    {
      int a, b;
      cin >> a >> b;
      g[a].push_back(b);
    }
  for (int i = 1; i <= n; i++)
    {
      if (!dfn[i])
        tarjan(i);
    }
  cout << cnt << endl;
}
signed main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin>>__;
  while (__--)
    {
      solve();
    }
  return 0;
}

acwing 受欢迎的牛（缩环成点）

/*********************************************************************
    程序名:
    版权:
    作者:
    日期: 2022-07-05 17:11
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
bool instack[N];
stack<int>s;
int timestamp;
int low[N];
int dfn[N];
int n, m;
vector<int>g[N];
int cnt;
int id[N];
int scccdu[N];
int sz[N];
void tarjan(int u)
{
  dfn[u] = low[u] = ++timestamp;
  s.push(u);
  instack[u] = true;
  for (auto j : g[u])
    {
      if (!dfn[j])
        {
          tarjan(j);
          low[u] = min(low[u], low[j]);
        }
      else if (instack[j])
        {
          low[u] = min(low[u], dfn[j]);
        }
    }
  if (dfn[u] == low[u])
    {
      int y;
      ++cnt;
      do
        {
          y = s.top();
          instack[y] = false;
          s.pop();
          id[y] = cnt;
          sz[cnt]++;
        }
      while (u != y);
    }
  return;
}
void solve()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
    {
      int a, b;
      cin >> a >> b;
      g[a].push_back(b);
    }
  for (int i = 1; i <= n; i++)
    {
      if (!dfn[i])
        tarjan(i);
    }
  int zero = 0, sum = 0;
  for (int i = 1; i <= n; i++)
    {
      for (int j : g[i])
        {
          int a = id[i];
          int b = id[j];
          if (a != b)
            {
              scccdu[a]++;
            }
        }
    }
  for (int i = 1; i <= cnt; i++)
    {
      if (!scccdu[i])
        {
          zero++;
          sum += sz[i];
          if (zero > 1)
            {
              sum = 0;
              break;
            }
        }
    }
  cout << sum << endl;
}
signed main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin>>__;
  while (__--)
    {
      solve();
    }
  return 0;
}

结论题:学校网络

在缩点之后，图为DAG，当整个图为强连通时，补的边为0，否则，想要整个图变为强连通图，需要补max(q,p)条有向边，p为入度为0的点个数，q为出度为0的点个数。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int>g[N];
bool instack[N];
stack<int>s;
int low[N],dfn[N],timestamp;
int id[N];
int cnt;
int n;
int din[N];
int dout[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    s.push(u);
    instack[u]=true;
    for(int j:g[u])
    {
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else if(instack[j])
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        int y;
        ++cnt;
        do
        {
            y=s.top();
            s.pop();
            instack[y]=false;
            id[y]=cnt;
        }while(y!=u);
    }
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int b;
        while(cin>>b,b)
        {
            g[i].push_back(b);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    int p=0,q=0;
    for(int i=1;i<=n;i++)
    {
        for(int j:g[i])
        {
            int x=id[i];
            int y=id[j];
            if(x!=y)
            {
                din[y]++;
                dout[x]++;
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        if(!din[i]) p++;
        if(!dout[i]) q++;
    }
    cout<<p<<endl;
    if(cnt==1) cout<<0<<endl;
    else
    cout<<max(p,q)<<endl;
}

最大半联通子图

注意缩点之后的建图后的判重边。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
typedef long long ll;
bool instack[N];
int low[N], dfn[N], timestamp;
int cnt, sz[N], id[N];
int n, m, mod;
vector<int>g[N], G[N];
stack<int>s;
int f[N];//i点结尾的最长链
int  p[N];//i点结尾的最长练的数量
void tarjan(int u)
{
  low[u] = dfn[u] = ++timestamp;
  s.push(u);
  instack[u] = true;
  for (int i : g[u])
    {
      if (!dfn[i])
        {
          tarjan(i);
          low[u] = min(low[u], low[i]);
        }
      else if (instack[i])
        {
          low[u] = min(low[u], dfn[i]);
        }
    }
  if (dfn[u] == low[u])
    {
      int node;
      ++cnt;
      do
        {
          node = s.top();
          s.pop();
          instack[node] = false;
          id[node] = cnt;
          sz[cnt]++;
        }
      while (node != u);
    }
}
int main()
{
  scanf("%d%d%d", &n, &m, &mod);
  for (int i = 1; i <= m; i++)
    {
      int a, b;
      scanf("%d%d", &a, &b);
      g[a].push_back(b);
    }
  for (int i = 1; i <= n; i++)
    {
      if (!dfn[i])
        tarjan(i);
    }
  unordered_set<ll>s;
  for (int i = 1; i <= n; i++)
    {
      for (int j : g[i])
        {
          int a = id[i];
          int b = id[j];
          if (a != b && !s.count(a * 100000ll + b))
            {
              G[a].push_back(b);
              s.insert(a * 100000ll + b);
            }
        }
    }
  for (int i = cnt; i ; i--)
    {
      if (!f[i])
        {
          f[i] = sz[i];
          p[i] = 1;
        }
      for (int j : G[i])
        {
          if (f[j] < f[i] + sz[j])
            {
              f[j] = f[i] + sz[j];
              p[j] = p[i];
            }
          else if (f[j] == f[i] + sz[j])
            {
              p[j] = (p[i] + p[j]) % mod;
            }
        }
    }
  int mx = 0, sum = 0;
  for (int i = 1; i <= cnt; i++)
    {
      if (f[i] > mx)
        {
          mx = f[i];
          sum = p[i];
        }
      else if (f[i] == mx)
        {
          sum = (sum + p[i]) % mod;
        }
    }
  cout << mx << endl;
  cout << sum << endl;
}

银河

差分约束+tarjan O(n+m) 写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node
{
  int x;
  int y;
};
vector<node>g[N], G[N];
int n, m;
typedef long long ll;
int timestamp, low[N], dfn[N];
bool instack[N];
int cnt, id[N], sz[N];
stack<int>s;
int dis[N];
void tarjan(int u)
{
  dfn[u] = low[u] = ++timestamp;
  s.push(u);
  instack[u] = true;
  //cout << 1 << endl;
  for (auto [x, y] : g[u])
    {
      if (!dfn[x])
        {
          tarjan(x);
          low[u] = min(low[u], low[x]);
        }
      else if (instack[x])
        low[u] = min(low[u], dfn[x]);
    }
  if (dfn[u] == low[u])
    {
      int node;
      ++cnt;
      do
        {
          node = s.top();
          s.pop();
          instack[node] = false;
          id[node] = cnt;
          sz[cnt]++;
        }
      while (node != u);
    }
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
    {
      int x, a, b;
      scanf("%d%d%d", &x, &a, &b);
      if (x == 1)
        {
          g[a].push_back({b, 0});
          g[b].push_back({a, 0});
        }
      else if (x == 2)
        {
          g[a].push_back({b, 1});
        }
      else if (x == 3)
        {
          g[b].push_back({a, 0});
        }
      else if (x == 4)
        {
          g[b].push_back({a, 1});
        }
      else
        {
          g[a].push_back({b, 0});
        }
    }
  for (int i = 1; i <= n; i++)
    g[0].push_back({i, 1});
  tarjan(0);
  bool ok = true;
  for (int i = 0; i <= n; i++)
    {
      for (auto [x, y] : g[i])
        {
          int a = id[i];
          int b = id[x];
          if (a == b)
            {
              if (y > 0)
                {
                  ok = false;
                  break;
                }
            }
          else
            {
              G[a].push_back({b, y});
            }
          if (!ok)
            break;
        }
    }
  if (!ok)
    {
      cout << -1 << endl;
      return 0;
    }
  memset(dis, -1, sizeof(dis));
  dis[cnt] = 0;
  for (int i = cnt; i >= 1; i--)
    {
      for (auto [x, y] : G[i])
        {
          if (dis[x] < dis[i] + y)
            {
              dis[x] = dis[i] + y;
            }
        }
    }
  ll res = 0;
  for (int i = 1; i <= cnt; i++)
    {
      res += 1LL * sz[i] * dis[i];
    }
  cout << res << endl;
}

差分约束+spfa写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node
{
  int x;
  int y;
};
vector<node>g[N];
int n, k;
bool st[N];
int cnt[N];
int d[N];
bool spfa()
{
  memset(d, -0x3f, sizeof(d));
  d[0] = 0;
  st[0] = true;
  queue<int>q;
  q.push(0);
  while (q.size())
    {
      auto t = q.front();
      q.pop();
      st[t] = false;
      for (auto [x, y] : g[t])
        {
          if (d[t] + y > d[x])
            {
              d[x] = d[t] + y;
              cnt[x] = cnt[t] + 1;
              if (cnt[x] >= n + 1)
                return false;
              if (!st[x])
                {
                  q.push(x);
                  st[x] = true;
                }
            }
        }
    }
  return true;
}
int main()
{
  cin >> n >> k;
  for (int i = 1; i <= k; i++)
    {
      int x, a, b;
        scanf("%lld%lld%lld",&x,&a,&b);
      if (x == 1)
        {
          g[a].push_back({b, 0});
          g[b].push_back({a, 0});
        }
      else if (x == 2)
        {
          g[a].push_back({b, 1});
        }
      else if (x == 3)
        {
          g[b].push_back({a, 0});
        }
      else if (x == 4)
        {
          g[b].push_back({a, 1});
        }
      else if (x == 5)
        {
          g[a].push_back({b, 0});
        }
    }
  //源点
  //x[i]>=1,x[i]>=x[0]+1,x[0]=0;
  for (int i = 1; i <= n; i++)
    {
      g[0].push_back({i, 1});
    }
  bool ok = spfa();
  if (ok)
    {
      long long  res = 0;
      for (int i = 1; i <= n; i++)
        {
          res += d[i];
        }
      cout << res << endl;
    }
  else
    {
      cout << -1 << endl;
    }
}

tarjan无向图求双连通分量模板：

#include<bits/stdc++.h>
using namespace std;
const int N=5100,M=21000;
int h[N],e[M],ne[M],idx;
int timestamp,low[N],dfn[N];
stack<int>s;
int dcc_cnt;
int id[N],d[N];
int n,m;
bool is_bridge[M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    s.push(u);
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(low[j]>dfn[u])
            {
                is_bridge[i]=is_bridge[i^1]=true;
            }
        }else if(i!=(from^1))
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        int y;
        ++dcc_cnt;
        do{
            y=s.top();
            s.pop();
            id[y]=dcc_cnt;
        }while(y!=u);
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    tarjan(1,-1);
    for(int i=0;i<idx;i++)
    {
        if(is_bridge[i])
        {
            d[id[e[i]]]++;
        }
    }
    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++)
    {
        if(d[i]==1) cnt++;
    }
    cout<<(cnt+1)/2<<endl;
}
蔡珏
目录
相关文章
博哥解答世间万物
|
11月前
|
人工智能
用好Deepseek
构建高效提问体系，让deepseek成为你的智商增量。通过高维提问，解锁其隐藏潜力，不再只是搬运答案。细节与认知厚度决定反馈质量，使用STAR法则（情景、任务、行动、结果）优化提问，AI不仅能提供答案，更能帮你搭建完整解决方案，提升认知水平。
博哥解答世间万物
594 73
游客bhmgxanbwhyfe
|
10月前
|
NoSQL Redis
Redis的数据淘汰策略有哪些 ?
Redis 提供 8 种数据淘汰策略： 淘汰易失数据(具有过期时间的数据) 1. volatile-lru（least recently used）：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰 2. volatile-lfu（least frequently used）：从已设置过期时间的数据集（server.db[i].expires）中挑选最不经常使用的数据淘汰 3. volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰 4. volatile-random：从已设置过期
游客bhmgxanbwhyfe
408 1
何雨晨
|
存储 IDE 开发工具
来咯，他来咯 看GitHub Codespaces 如何帮助缩短开发设置时间
来咯，他来咯 看GitHub Codespaces 如何帮助缩短开发设置时间
何雨晨
855 1
萝卜带泥
|
机器学习/深度学习 缓存 运维
智能化运维：机器学习在IT管理中的革命性应用
【8月更文挑战第28天】 随着技术的飞速发展，传统的IT运维方式已不能满足现代企业的需求。智能化运维，通过整合机器学习技术，正在重塑我们对IT基础设施的管理方法。本文将探讨智能化运维的概念、实施步骤及其带来的变革，同时分享一些成功案例，以期为读者提供一种全新的视角和思考路径。
萝卜带泥
167 6
土木林森
|
运维 应用服务中间件 Apache
震撼登场！Ansible roles 化身自动化运维神器，打破传统束缚，开启运维新时代！
【8月更文挑战第9天】Ansible是一款强大的自动化运维工具，其Roles功能将复杂任务分解为可复用模块，提升代码的可读性、可维护性和可扩展性。通过创建结构化的目录，如tasks、handlers和vars等，可以清晰地组织配置与任务。例如，为Web服务器创建一个Role，包含安装Apache、启动服务等任务，并可在不同的Playbook中重复使用此Role，简化大型集群的配置管理工作，提高效率和质量。
土木林森
194 6
泡沫o0
|
存储 安全 Shell
【Shell 命令集合 磁盘维护】Linux 检测和识别硬盘或文件系统中的坏块 badblocks命令使用教程
【Shell 命令集合 磁盘维护】Linux 检测和识别硬盘或文件系统中的坏块 badblocks命令使用教程
泡沫o0
689 0
赵舒涵
|
存储 算法 C语言
C语言查找字符
C语言查找字符
赵舒涵
252 0
人才程序员
|
存储 算法 容器
【C++11算法】is_sorted、is_sorted_until
【C++11算法】is_sorted、is_sorted_until
人才程序员
211 0
路宇
|
定位技术 Android开发 芯片
Android 中获取LocationProvider的三种方法和获取定位信息
Android 中获取LocationProvider的三种方法和获取定位信息
路宇
1539 0
开发者小助理
|
程序员 开发者
《程序员请回答——职场话题篇》视频征集活动来啦，参与即送100元现金！
视频征集活动开启，作品围绕“程序员职场”话题方向，讲述求职面试过程中的技巧、经验和感悟等。本次活动，成功参与投稿的创作者，均可获得100元现金！ 更有2000元现金大奖等你拿！
开发者小助理
710 1
《程序员请回答——职场话题篇》视频征集活动来啦，参与即送100元现金！

热门文章

最新文章

  • 1
    【Centos】-bash: warning: setlocale: LC_CTYPE: cannot change locale (“zh_CN.UTF-8”): No such file o...
  • 2
    阿里云服务器创建历史功能介绍 快速创建云服务器
  • 3
    RNN和LSTM弱！爆！了！注意力模型才是王道
  • 4
    从无到有搭建Macaca环境(for Mac)
  • 5
    编程必备，程序员应该都知道的7款文本编辑器
  • 6
    拍立淘---试妆魔镜 OpenGL ES 2.0 框架及性能优化
  • 7
    HIVE的安装配置、mysql的安装、hive创建表、创建分区、修改表等内容、hive beeline使用、HIVE的四种数据导入方式、使用Java代码执行hive的sql命令
  • 8
    拜托，别再问我什么是B+树 了
  • 9
    编程哲学
  • 10
    中国科技工作者之家“科猫”平台上线，科技工作者的机遇
  • 1
    阿里云服务器租赁价格2026年哪里看？一年/按月/按小时收费贵吗？
    44
  • 2
    2026年阿里云服务器活动，云服务器租用价格多少钱一年？
    53
  • 3
    2025年商用轮式机器人技术解析与选型指南
    48
  • 4
    2026年阿里云 8 核 16G 云服务器解析测评：实例特性、收费标准与成本优化
    58
  • 5
    一线工程师 2025 总结：LLM 只用了不到 10%，剩下 90% 卡在哪？
    60
  • 6
    阿里云万小智建站怎么样？有用过的吗？AI建站收费价格及版本功能介绍
    34
  • 7
    阿里云高配置云服务器解析：4 核 16G、8 核 16G、8 核 32G 实例特性与价格说明
    49
  • 8
    阿里云第八代2核4G、4核8G、2核8G、4核16G、2核16G和4核32G服务器测评：实例特性、优惠价格与适用场景
    35
  • 9
    NPP 热带森林：委内瑞拉 San Carlos de Rio Negro，1975-1984 年，R1
    24
  • 10
    2026阿里云万小智AI建站收费价格查询系统：不同版本费用清单获取方法
    41

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    【DataEase】零代码数据可视化分析工具的安装部署保姆级教程