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

tarjan求强连通分量

2024-01-10 30
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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;
}
蔡珏
目录
相关文章
cheems~
|
6月前
|
算法
最短路之Floyd算法
最短路之Floyd算法
cheems~
74 1
小王老师呀
|
5月前
|
算法
Tarjan 求有向图的强连通分量
Tarjan算法是一种用于查找有向图中强连通分量的高效方法。作者分享了自己的笔记，强调了网上解释的不清晰性，并引用了OI Wiki的资源。算法维护每个节点的`dfn`(深度优先搜索顺序)和`low`(能到达的最小DFS序)。通过遍历节点和其邻接节点，更新`low`值，识别环路。当`dfn[x] == low[x]`，表示找到一个强连通分量。代码示例展示了具体的实现细节。
小王老师呀
35 0
静渊隐者
|
存储 算法 数据建模
【最短路算法】SPFA
【最短路算法】SPFA
静渊隐者
96 0
wtke75czg4pji
|
算法
SPFA算法-最短路-负环
SPFA算法-最短路-负环
wtke75czg4pji
84 0
cheems~
|
6月前
|
存储 算法
最短路之SPFA算法
最短路之SPFA算法
cheems~
54 0
钊气蓬勃.
|
算法 C++
用prim和kruskal算法求最小生成树问题
用prim和kruskal算法求最小生成树问题
钊气蓬勃.
81 0
钊气蓬勃.
|
C++
spfa处理差分约束
spfa处理差分约束
钊气蓬勃.
42 0
游客ubq3lfmyh64jm
邻接表存图 SPFA
邻接表存图 SPFA
游客ubq3lfmyh64jm
39 0
zzqwtc
最短路之Dijkstra+堆优化（单源最短路）
笔记
zzqwtc
97 0
ぃ灵彧が
|
算法
图论最短路及生成树(Prim,Djikstra,Spfa,Bellan-ford,kruskal,topsort)
图论最短路及生成树(Prim,Djikstra,Spfa,Bellan-ford,kruskal,topsort)
ぃ灵彧が
139 1