Tarjan整理
概括一下
-
强连通分量
1
2
3
4
5
6
7if(!V[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
} -
点双连通分量
1
2
3if(low[v]>=dfn[u]){
记录一个答案;
} -
边双连通分量
1
2
3
4
5
6if(low[v]>dfn[u]){
把 u<->v 这条边删掉;
}
int main(){
洪水填充找连通块;
} -
割点（割顶）
1
还是寒假讲的，真的忘了当初怎么想的了……
Code
-
强连通分量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#include<bits/stdc++.h>
using namespace std;
vector<int>G[50001];
int n,m,tot,at;
bool vis[50001],V[50001];
int dfn[50001];
int low[50001];
vector<int>ans[50001];
stack<int>s;
void tarjan(int u){
s.push(u);
V[u]=true;
vis[u]=true;
dfn[u]=++tot;
low[u]=dfn[u];
for(auto v:G[u]){
if(!V[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
at++;
int tmp;
do{
tmp=s.top();
ans[at].push_back(tmp);
vis[tmp]=false;
s.pop();
}while(!s.empty()&&tmp!=u);
}
}
int main(){
#ifdef USE_FILE_IO
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
#endif
cin>>n>>m;
for(int i=1;i<=m;i++){
int op,u,v;
cin>>u>>v;
G[u].push_back(v);
}
for(int i=1;i<=n;i++){
tot=0;
if(!V[i])tarjan(i);
}
cout<<at<<endl;
for(int i=1;i<=at;i++){
sort(ans[i].begin(),ans[i].end());
// if(ans[i].size()>mx){
// mx=ans[i].size();
// mxw=i;
// }
}
sort(ans+1,ans+at+1);
for(int i=1;i<=at;i++){
for(auto j:ans[i]){
cout<<j<<" ";
}
cout<<endl;
}
return 0;
} -
点双连通分量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=500005;
int n,m,idx;
vector<int>G[N];
int dfn[N],low[N];
stack<int>s;
int ansCnt;
vector<int>ans[N];
void tarjan(int fa,int u){
s.push(u);
dfn[u]=low[u]=++idx;
for(auto v:G[u]){
if(v==fa)continue;
if(!dfn[v]){
tarjan(u,v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
ansCnt++;
// while(s.top()!=u){
// ans[ansCnt].push_back(s.top());
// s.pop();
// }
int tmp;
do{
tmp=s.top();
ans[ansCnt].push_back(tmp);
s.pop();
}while(tmp!=v);
ans[ansCnt].push_back(u);
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==-1&&G[u].size()==0){
ansCnt++;
ans[ansCnt].push_back(u);
}
}
signed main(){
#ifdef USE_FILE_IO
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
#endif
// cin>>n>>m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
// cin>>u>>v;
scanf("%d%d",&u,&v);
if(u!=v){
G[u].push_back(v);
G[v].push_back(u);
}
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
// idx=0;
while(!s.empty())s.pop();
tarjan(-1,i);
}
}
printf("%d\n",ansCnt);
for(int i=1;i<=ansCnt;i++){
printf("%d ",ans[i].size());
for(auto j:ans[i]){
printf("%d ",j);
}
printf("\n");
}
return 0;
} -
边双连通分量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,m,idx;
vector<int>G[N];
int dfn[N],low[N];
stack<int>s;
int ansCnt;
vector<int>ans[N];
unordered_map<int,int>bridge;
unordered_map<int,int>edge;
unordered_map<int,int>ok;
void tarjan(int fa,int u){
s.push(u);
dfn[u]=low[u]=++idx;
for(auto v:G[u]){
if(v==fa)continue;
if(!dfn[v]){
tarjan(u,v);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
bridge[u*N+v]=!ok[u*N+v];
bridge[v*N+u]=!ok[u*N+v];
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
bool vis[N];
void dfs(int u){
vis[u]=1;
ans[ansCnt].push_back(u);
for(auto v:G[u]){
if(!vis[v]&&(!bridge[u*N+v])){
dfs(v);
}
}
}
signed main(){
#ifdef USE_FILE_IO
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
#endif
// cin>>n>>m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
// cin>>u>>v;
scanf("%lld%lld",&u,&v);
if(u!=v&&!edge[u*N+v]){
G[u].push_back(v);
G[v].push_back(u);
edge[u*N+v]=1;
edge[v*N+u]=1;
}
else if(u!=v){
ok[u*N+v]=1;
ok[v*N+u]=1;
}
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(-1,i);
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){
ansCnt++;
dfs(i);
}
}
printf("%lld\n",ansCnt);
for(int i=1;i<=ansCnt;i++){
printf("%ld ",ans[i].size());
for(auto j:ans[i]){
printf("%lld ",j);
}
printf("\n");
}
return 0;
} -
割点（割顶）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include<bits/stdc++.h>
using namespace std;
const int maxn=20000;
vector<int>G[maxn+100];
int dfn[maxn+100],low[maxn+100],tot;
int n,m;
vector<int>cut;
void Tarjan(int u,int root){
low[u]=dfn[u]=++tot;
int cnt=0;
for(auto v:G[u]){
if(!dfn[v]){
Tarjan(v,root);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])cnt++;
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(u==root){
if(cnt>1)cut.push_back(u);
}
else
if(cnt>0)cut.push_back(u);
}
int main(){
#ifdef USE_FILE_IO
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
#endif
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(dfn[i])continue;
Tarjan(i,i);
}
sort(cut.begin(),cut.end());
cout<<cut.size()<<endl;
for(int i=0;i<cut.size();i++)
cout<<cut[i]<<" ";
return 0;
}
Tarjan整理
https://shicj.pages.dev/2025/01/01/Tarjan整理/