欢迎来看 “片” (的简介)
由于-\(看片\)-生涯转瞬即逝,于是我选择对“\(片\)”进行一定的总结:
相信你一定看懂了
由于开始的时间有一点晚,就姑且认为我以后会慢慢补充吧......
回到总部
\(B3609\) \([图论与代数结构\) \(701]\) \(强连通分量\)
解:tarjan,强连通分量
\(\mathcal{RT}\)
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define endl '\n'
using namespace std;
const int MAXM=1e5+5;
const int MAXN=1e4+5;
ll n,m;
struct edge{
ll to,nxt;
};
edge e[MAXM];
ll head[MAXN],tot=0;
void add_edge(ll u,ll v){
++tot;
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot;
}
ll colsum=0,dfn[MAXN],low[MAXN],stk[MAXN],vis[MAXN],dep=0,col[MAXN];
vector <ll> ans[MAXN];
void tarjan(ll u){
dfn[u]=++dep;
low[u]=dep;
stk[++stk[0]]=u;
vis[u]=1;
for (int i=head[u];i;i=e[i].nxt){
ll v=e[i].to;
if (!dfn[v]){
tarjan(v);
low[u]=min(low[v],low[u]);
}
else{
if (vis[v]){
low[u]=min(low[v],low[u]);
}
}
}
if (low[u]!=dfn[u]){
return;
}
// cout<<u<<endl;
++colsum;
vis[u]=0;
ans[colsum].push_back(u);
while (stk[stk[0]]!=u){
vis[stk[stk[0]]]=0;
ans[colsum].push_back(stk[stk[0]]);
col[stk[stk[0]]]=colsum;
--stk[0];
}
--stk[0];
col[u]=colsum;
}
bool flag[MAXN];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for (int i=1;i<=m;i++){
ll u,v;
cin>>u>>v;
add_edge(u,v);
}
for (int i=1;i<=n;i++){
if (!dfn[i]) tarjan(i);
}
for (int i=1;i<=colsum;i++){
sort(ans[i].begin(),ans[i].end());
}
cout<<colsum<<endl;
for (int i=1;i<=n;i++){
if (!flag[col[i]]){
for (auto a:ans[col[i]])
cout<<a<<" ";
flag[col[i]]=1;
cout<<endl;
}
}
}
Tips
- 当发现可以建无向图的时候,不妨再想一想能否用并查集