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

算法提高模板强连通分量tarjan算法

news 来源：原创 2024/9/18 8:49:56

在这里插入图片描述

AC代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;
const int MOD = 998244353;
const int N = 2e5 + 10;//强联通分量模板
//tarjan算法
vector<int>e[N];
int n, m, cnt;
int dfn[N], low[N], ins[N], idx;
int bel[N];//记录每个点在哪一个强连通分量里
stack<int>stk;
vector<vector<int>>scc;
void tarjan(int u)
{dfn[u] = low[u] = ++ idx;//时间戳；ins[u] = true;//有没有被切掉stk.push(u);for(auto v : e[u]){if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else {if(ins[v]) low[u] = min(low[u], dfn[v]);}}if(dfn[u] == low[u])//一个强连通分量{vector<int>c;++cnt;//记录每个点到底在哪一个连通块里while(1){int v = stk.top();bel[v] = cnt;c.push_back(v);stk.pop();if(v == u) break;}sort(c.begin(), c.end());//题目要求字典序scc.push_back(c);//存下来每一个连通块}
}int main()
{cin >> n >> m;for(int i = 1; i <= m; i ++){int u, v;cin >> u >> v;e[u].push_back(v);}//有向边for(int i = 1; i <= n; i ++){if(!dfn[i]) tarjan(i);}sort(scc.begin(), scc.end());for(auto it : scc){for(auto c : it){cout << c << " ";}cout << endl;}
}

受欢迎的牛：

在这里插入图片描述

带注释的代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;
const int MOD = 998244353;
const int N = 2e5 + 10;//tarjan
vector<int>e[N];
int n, m, cnt;//cnt代表强连通分量的总数
int dfn[N];//记录时间戳；
int low[N];//记录每个连通块内的最小节点
int ins[N];//记录有没有被切割掉
int idx;//时间戳的标号
int bel[N];//记录每个点在哪一个强联通分量里
stack<int>stk;//储存每个强连通块的点
vector<vector<int>>scc;//储存每个强连通块
int outd[N];//储存每个强连通块的出度
int sz[N];//第i个强联通块的点数void  tarjan(int u)
{dfn[u] = low[u] = ++ idx;//记录时间戳ins[u] = 1;//记录遍历过了stk.push(u);//存点for(auto v : e[u]){if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else{if(ins[v])low[u] = min(low[u], dfn[v]);//记录连通块内的最小点，方便辨认是不是同一个连通块}}if(dfn[u] == low[u]){vector<int>c;//存每一个连通块的小数组++ cnt;//连通块的下标while(1){int v = stk.top();bel[v] = cnt;//记录每个点到底在哪一个连通块内sz[cnt] ++;//每个联通块点的数量c.push_back(v);stk.pop();if(u == v) break;//说明遍历完了该连通块}sort(c.begin(), c.end());//题目要求scc.push_back(c);//存下每个连通块}
}
int main()
{cin >> n >> m;//输入for(int i = 1; i <= m; i ++){int u, v;cin >> u >> v;e[u].push_back(v);//输入有向边}for(int i = 1; i <= n; i ++){if(!dfn[i]) tarjan(i);//对每一个点进行讨论，相当于求连通块然后在这部进行操作罢了}sort(scc.begin(), scc.end());//题目说按照最小字典序for(int u = 1; u <= n; u ++)//计算每一个点的出度{for(auto v : e[u]){if(bel[u] != bel[v]) outd[bel[u]] ++;//出度加1}}int cnts = 0, cntv = 0;for(int i = 1; i <= cnt; i ++){if(outd[i] == 0)//如果第i个强连通分量出度 == 0{cnts ++;cntv += sz[i];//则加上第i个强连通分量的点的个数}}if(cnts >= 2)//则不满足题意{puts("0");}else cout << cntv << endl;//满足条件的牛的个数
}