哦，是tarjan。
题单
割边判定
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn];
ll head[maxn],dfn[maxn],low[maxn],tmp,cnt,n,m;
bool bridge[maxn];
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void tarjan(ll x,ll faedge){
dfn[x]=low[x]=cnt++;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
bridge[i]=bridge[i^1]=true;
}
}
else if(i != (faedge ^ 1)){
low[x]=min(low[x],dfn[y]);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tmp = 2;cnt=1;
for (ll i = 1; i <= m; i++) {
ll x, y;cin>>x>>y;
add(x, y), add(y, x);
}
for (ll i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, 0);
for (ll i = 2; i < tmp; i += 2)
if (bridge[i])
cout<<edge[i^1].to<<" "<<edge[i].to<<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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn];
ll head[maxn],dfn[maxn],low[maxn],tmp,cnt,n,m,root;
vector<ll> v;
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void tarjan(ll x){
dfn[x]=low[x]=cnt++;
ll flag=0;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
flag++;
if(x!=root || flag>=2) v.push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void solve(){
for(ll i=1;i<=n;i++){
if(!dfn[i]) {root=i;tarjan(i);}
}
sort(v.begin(),v.end());
auto en=unique(v.begin(),v.end());
cout<<en-v.begin()<<endl;
for(auto i=v.begin();i!=en;i++) cout<<*i<<" ";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
tmp=1;cnt=1;
for(ll i=1,x,y;i<=m;i++){
cin>>x>>y;
if(x==y) continue;
add(x,y);
}
solve();
return 0;
}
|
边双连通分量e-dcc
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn];
ll head[maxn],dfn[maxn],low[maxn],c[maxn],dcc,tmp,cnt,n,m;
bool bridge[maxn];
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void tarjan(ll x,ll faedge){
dfn[x]=low[x]=cnt++;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
bridge[i]=bridge[i^1]=true;
}
}
else if(i != (faedge ^ 1)){
low[x]=min(low[x],dfn[y]);
}
}
}
void dfs(ll x){
c[x]=dcc;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(c[y] || bridge[i]) continue;
dfs(y);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tmp = 2;cnt=1;dcc=1;
for (ll i = 1; i <= m; i++) {
ll x, y;cin>>x>>y;
add(x, y), add(y, x);
}
for (ll i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, 0);
for (ll i = 2; i < tmp; i += 2)
if (bridge[i])
cout<<edge[i^1].to<<" "<<edge[i].to<<endl;
for(ll i=1;i<=n;i++){
if(!c[i]){
dfs(i);
dcc++;
}
}
Debug(dcc-1);
for(ll i=1;i<=n;i++) cout<<i<<"belongs to DCC "<<c[i]<<endl;
return 0;
}
|
边双连通分量e-dcc缩点
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll fr,to,next;
}edge[maxn],edgesk[maxn];
ll head[maxn],headsk[maxn],dfn[maxn],low[maxn],c[maxn],dcc,tmp,tmpsk,cnt,n,m;
bool bridge[maxn];
void add(ll u,ll v){
edge[tmp]={u,v};edge[tmp].next=head[u];
head[u]=tmp++;
}
void addsk(ll u,ll v){
edgesk[tmpsk]={u,v};edgesk[tmpsk].next=headsk[u];
headsk[u]=tmpsk++;
}
void tarjan(ll x,ll faedge){
dfn[x]=low[x]=cnt++;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
bridge[i]=bridge[i^1]=true;
}
}
else if(i != (faedge ^ 1)){
low[x]=min(low[x],dfn[y]);
}
}
}
void dfs(ll x){
c[x]=dcc;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(c[y] || bridge[i]) continue;
dfs(y);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tmp=tmpsk=2;cnt=1;dcc=1;
for (ll i = 1; i <= m; i++) {
ll x, y;cin>>x>>y;
add(x, y), add(y, x);
}
for (ll i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, 0);
for (ll i = 2; i < tmp; i += 2)
if (bridge[i])
cout<<edge[i^1].to<<" "<<edge[i].to<<endl;
for(ll i=1;i<=n;i++){
if(!c[i]){
dfs(i);
dcc++;
}
}
Debug(dcc-1);
for(ll i=1;i<=n;i++) cout<<i<<" belongs to DCC "<<c[i]<<endl;
for(ll i=2;i<tmp;i++){
ll u=edge[i].fr,v=edge[i].to;
if(c[u]==c[v]) continue;
addsk(c[u],c[v]);
}
return 0;
}
|
点双连通分量v-dcc
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn];
ll head[maxn],dfn[maxn],low[maxn],st[maxn],tmp,cnt,num,n,m,root,top;
vector<ll> dcc[maxn];
bool cut[maxn];
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void tarjan(ll x){
dfn[x]=low[x]=cnt++;
st[top++]=x;
if(x==root && head[x]==0){
dcc[num++].push_back(x);return ;
}
ll flag=0;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
flag++;
if(x!=root || flag>=2) cut[x]=true;
ll z;
do{
z=st[--top];
dcc[num].push_back(z);
}while(z!=y);
dcc[num++].push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void solve(){
for(ll i=1;i<=n;i++){
if(!dfn[i]) {root=i;tarjan(i);}
}
for(ll i=1;i<num;i++){
for(auto j=dcc[i].begin();j!=dcc[i].end();j++) cout<<*j<<" ";
cout<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
tmp=1;cnt=1;num=1;top=1;
for(ll i=1,x,y;i<=m;i++){
cin>>x>>y;
if(x==y) continue;
add(x,y);add(y,x);
}
solve();
return 0;
}
|
点双连通分量v-dcc缩点
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
85
86
87
88
89
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn],edgesk[maxn];
ll head[maxn],headsk[maxn],dfn[maxn],low[maxn],st[maxn],c[maxn],n_id[maxn];
ll tmp,tmpsk,cnt,num,n,m,root,top;
vector<ll> dcc[maxn];
bool cut[maxn];
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void addsk(ll u,ll v){
edgesk[tmpsk].to=v;edgesk[tmpsk].next=headsk[u];
headsk[u]=tmpsk++;
}
void tarjan(ll x){
dfn[x]=low[x]=cnt++;
st[top++]=x;
if(x==root && head[x]==0){
dcc[num++].push_back(x);return ;
}
ll flag=0;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
flag++;
if(x!=root || flag>=2) cut[x]=true;
ll z;
do{
z=st[--top];
dcc[num].push_back(z);
}while(z!=y);
dcc[num++].push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void solve(){
for(ll i=1;i<=n;i++){
if(!dfn[i]) {root=i;tarjan(i);}
}
for(ll i=1;i<num;i++){
for(auto j=dcc[i].begin();j!=dcc[i].end();j++) cout<<*j<<" ";
cout<<endl;
}
cnt=num;
for(ll i=1;i<=n;i++) if(cut[i]) n_id[i]=cnt++;
tmpsk=1;
for(ll i=1;i<num;i++){
for(auto j=dcc[i].begin();j!=dcc[i].end();j++){
ll x=*j;
if(cut[x]){
addsk(i,n_id[x]);addsk(n_id[x],i);
}
else c[x]=i;
}
}
Debug(cnt);Debug(tmpsk/2);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
tmp=1;cnt=1;num=1;top=1;
for(ll i=1,x,y;i<=m;i++){
cin>>x>>y;
if(x==y) continue;
add(x,y);add(y,x);
}
solve();
return 0;
}
|
求环(每条边至多被一个环包围)
这个求环可以用点双连通分量写
也可以先跑个树出来，同时标记每个点的深度,注意不是dfs序！！！，（考虑一个环外延伸出一个点的情况）,然后再加上非树的边构成环，环的边数就是两点深度之差+1。
Forest Program
题解
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e6+11;
const ll mod=998244353;
struct Edge{
ll fr,to,next;
}edge[maxn];
ll head[maxn],dfn[maxn],vis[maxn],qp2[maxn],tmp=2,cnt=1,m;
void add(ll u,ll v){
edge[tmp]={u,v};edge[tmp].next=head[u];
head[u]=tmp++;
}
void dfs(ll u){
for(ll i=head[u];i;i=edge[i].next){
ll v=edge[i].to;
if(!dfn[v]){
dfn[v]=dfn[u]+1;
vis[i]=vis[i^1]=1;dfs(v);
}
}
}
void solve(){
ll l=0,ans=1;
for(ll i=2;i<tmp;i+=2){
if(!vis[i]){
ll u=edge[i].fr,v=edge[i].to;
ll t=abs(dfn[u]-dfn[v])+1;
l+=t;
ans=ans*(qp2[t]-1)%mod;
}
}
ans=ans*qp2[tmp/2-1-l]%mod;
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
qp2[0]=1;
for(ll i=1;i<maxn;i++) qp2[i]=qp2[i-1]*2%mod;
ll n;cin>>n>>m;
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;
add(u,v);add(v,u);
}
for(ll i=1;i<=n;i++){
if(!dfn[i]) dfn[i]=1,dfs(i);
}
solve();
return 0;
}
|
缩点树度数
Road Construction
题意：求缩点树中度数为1的个数
这个有几种写法：
1.
1
2
3
4
5
6
7
| for(ll i=1;i<=n;i++){
for(ll j=head[i];j;j=edge[j].next){
if(low[i]!=low[edge[j].to]){
re[low[i]]++;
}
}
}
|
这种写法，只能用来求度数为1的点个数，度数为其他不能求，因为同一个边连通分量的low值不一定一样。
2.
1
2
3
4
5
6
| for(ll i=2;i<tmp;i++){
if(bridge[i]){
ll v=edge[i].to;
re[c[v]]++;
}
}
|
这种写法，就是把它的缩点的块标号，来求每个缩点的度数，是最稳的。
一个错误写法：
3.
1
2
3
4
5
6
| for(ll i=2;i<tmp;i++){
if(bridge[i]){
ll v=edge[i].to;
re[low[v]]++;
}
}
|
因为同一个边连通分量的low值不一定是一样的
缩点所连接的连通块个数
Electricity(POJ2117)
题意：一张图，不一定连通。问，删去一个点，最多可以有多少个连通块。
题解：找割点，答案是一开始连通分量个数+割点可产生的最多连通分量的个数。
注意m==0的情况，因为必须要删除一个点，所以输出n-1。
核心代码：if(u!=root || flag>=2) cut[u]++;
最终缩点u所连接的连通块个数为cut[u]+1。因为最开始dfs到u的那条边，没有被统计到
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
|
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e4+11;
const ll maxm=1e6+11;
ll to[maxm],nex[maxm],head[maxn],dfn[maxn],low[maxn],cut[maxn];
ll tmp,cnt,root,n,m;
void init(){
memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));
memset(cut,0,sizeof(cut));
tmp=2,cnt=1;
}
void add(ll u,ll v){
to[tmp]=v;nex[tmp]=head[u];head[u]=tmp++;
}
void tarjan(ll u){
dfn[u]=low[u]=cnt++;
ll flag=0;
for(ll i=head[u];i;i=nex[i]){
ll v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
flag++;
if(u!=root || flag>=2) cut[u]++;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void solve(){
ll ansf=0,anss=0;
for(ll i=0;i<n;i++){
if(!dfn[i]){
ansf++;root=i;tarjan(i);
}
}
for(ll i=0;i<n;i++) anss=max(anss,cut[i]);
if(anss==0){
if(m==0){
cout<<ansf-1<<endl;return ;
}
else{
cout<<ansf<<endl;return ;
}
}
cout<<ansf+anss<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n>>m && (n||m)){
init();
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;
add(u,v);add(v,u);
}
solve();
}
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
|
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn];
ll head[maxn],dfn[maxn],low[maxn],c[maxn],st[maxn],ins[maxn];
ll tmp,top,cnt,num,n,m;
vector<ll> scc[maxn];
bool bridge[maxn];
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void tarjan(ll x){
dfn[x]=low[x]=cnt++;
st[top++]=x;ins[x]=1;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[x]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
num++;ll y;
do{
y=st[--top],ins[y]=0;
c[y]=num;scc[num].push_back(y);
}while(x!=y);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tmp = 2;cnt=1;num=0;top=1;
for (int i = 1; i <= m; i++) {
int x, y;cin>>x>>y;
add(x, y);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(ll i=1;i<=num;i++){
for(auto j=scc[i].begin();j!=scc[i].end();j++) 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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
ll to,next;
}edge[maxn],edgesk[maxn];
ll head[maxn],headsk[maxn],dfn[maxn],low[maxn],c[maxn],st[maxn],ins[maxn];
ll tmp,tmpsk,top,cnt,num,n,m;
vector<ll> scc[maxn];
bool bridge[maxn];
void add(ll u,ll v){
edge[tmp].to=v;edge[tmp].next=head[u];
head[u]=tmp++;
}
void addsk(ll u,ll v){
edgesk[tmpsk].to=v;edgesk[tmpsk].next=headsk[u];
headsk[u]=tmpsk++;
}
void tarjan(ll x){
dfn[x]=low[x]=cnt++;
st[top++]=x;ins[x]=1;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[x]){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
num++;ll y;
do{
y=st[--top],ins[y]=0;
c[y]=num;scc[num].push_back(y);
}while(x!=y);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
tmp = 2;cnt=1;num=0;top=1;
for (int i = 1; i <= m; i++) {
int x, y;cin>>x>>y;
add(x, y);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(ll i=1;i<=num;i++){
for(auto j=scc[i].begin();j!=scc[i].end();j++) cout<<*j<<" ";
cout<<endl;
}
tmpsk=1;
for(ll x=1;x<=n;x++){
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].to;
if(c[x]==c[y]) continue;
addsk(c[x],c[y]);
}
}
return 0;
}
|
强连通分量缩点基础题
Summer Holiday HDU - 1827
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
|
#include<iostream>
#include<cstring>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e3+11;
ll fr[maxn],to[maxn],nex[maxn],head[maxn];
ll st[maxn],in[maxn],dfn[maxn],low[maxn],c[maxn],dr[maxn],val[maxn],w[maxn];
ll tmp,cnt,top,num,n,m;
void add(ll u,ll v){
fr[tmp]=u;to[tmp]=v;nex[tmp]=head[u];head[u]=tmp++;
}
void tarjan(ll u){
dfn[u]=low[u]=cnt++;in[u]=1;st[top++]=u;
for(ll i=head[u];i;i=nex[i]){
ll v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
num++;ll v;
do{
v=st[--top];in[v]=0;
c[v]=num;w[num]=min(w[num],val[v]);
}while(u!=v);
}
}
void solve(){
for(ll i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(ll i=1;i<tmp;i++){
ll u=fr[i],v=to[i];
if(c[u]==c[v]) continue;
dr[c[v]]++;
}
ll ans1=0,ans2=0;
for(ll i=1;i<=num;i++){
if(dr[i]==0){
ans1++;
ans2+=w[i];
}
}
cout<<ans1<<" "<<ans2<<endl;
}
void init(){
memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));
memset(c,0,sizeof(c));memset(dr,0,sizeof(dr));
memset(w,0x3f,sizeof(w));
tmp=cnt=1;num=0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n>>m){
init();
for(ll i=1;i<=n;i++) cin>>val[i];
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;add(u,v);
}
solve();
}
return 0;
}
|
建强连通图-巧写dfs序
这道题与求环那道题有点类似，都需要用到dfs序,不过这道题代码写法还是挺巧妙的。
Street Directions(POJ1515)
题意：一个无向连通图，最多能把多少条边改为有向边，使得剩下的图仍然是一个强连通分量。输出剩下的边。
点击查看思路
剩下的无向边必是割边，剩下那些边，会在某个边连通分量，每个边连通分量里的边都可以是有向边，仍然能互相到达，所以tarjan找到所有割边，dfs的顺序就作为有向边的方向即可。
这个是以dfs序号作为判断，树上的边是dfs序小向dfs序大建边，非树上的边是dfs序大向dfs序小建边
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
|
#include<iostream>
#include<cstring>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e3+11;
const ll maxm=2e6+11;
ll to[maxm],nex[maxm],head[maxn],dfn[maxn],low[maxn],d[maxn];
ll n,m,cnt,num,tmp;
bool bridge[maxm],t[maxm];
void add(ll u,ll v){
to[tmp]=v;nex[tmp]=head[u];head[u]=tmp++;
}
void tarjan(ll u,ll fue){
dfn[u]=low[u]=cnt++;
for(ll i=head[u];i;i=nex[i]){
ll v=to[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]) bridge[i]=bridge[i^1]=true;
}
else if(i!=(fue^1)) low[u]=min(low[u],dfn[v]);
}
}
void dfs(ll u){
d[u]=num++;
for(ll i=head[u];i;i=nex[i]){
ll v=to[i];
if(!d[v]){
t[i]=t[i^1]=true;
dfs(v);
}
}
}
void solve(){
tarjan(1,0);
dfs(1);
for(ll i=2;i<tmp;i+=2){
ll u=to[i],v=to[i^1];
if(t[i]){
if(d[u]<d[v]) cout<<u<<" "<<v<<endl;
else cout<<v<<" "<<u<<endl;
if(bridge[i]){
if(d[u]<d[v]) cout<<v<<" "<<u<<endl;
else cout<<u<<" "<<v<<endl;
}
}
else{
if(d[u]<d[v]) cout<<v<<" "<<u<<endl;
else cout<<u<<" "<<v<<endl;
}
}
}
void init(){
memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));
memset(d,0,sizeof(d));memset(bridge,0,sizeof(bridge));
memset(t,0,sizeof(t));
cnt=num=1;tmp=2;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ca=1;
while(cin>>n>>m && (n||m)){
cout<<ca++<<endl<<endl;
init();
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;add(u,v);add(v,u);
}
solve();
cout<<'#'<<endl;
}
return 0;
}
|
由于tarjan本身就是一个dfs的过程，所以没有必要再写一遍dfs。
所以直接在tarjan过程中标记边即可。
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
|
#include<iostream>
#include<cstring>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e3+11;
const ll maxm=2e6+11;
int to[maxm],nex[maxm],head[maxn],dfn[maxn],low[maxn],bridge[maxm];
ll n,m,cnt,tmp;
void add(ll u,ll v){
to[tmp]=v;nex[tmp]=head[u];head[u]=tmp++;
}
void tarjan(ll u,ll fue){
dfn[u]=low[u]=cnt++;
for(ll i=head[u];i;i=nex[i]){
ll v=to[i];
if(bridge[i]==0){
bridge[i]=1;
bridge[i^1]=-1;
}
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]) bridge[i]=bridge[i^1]=1;
}
else if(i!=(fue^1)) low[u]=min(low[u],dfn[v]);
}
}
void solve(){
tarjan(1,0);
for(ll i=2;i<tmp;i++) if(bridge[i]==1) cout<<to[i^1]<<" "<<to[i]<<endl;
}
void init(){
memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));
memset(bridge,0,sizeof(bridge));
cnt=1;tmp=2;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ca=1;
while(cin>>n>>m && (n||m)){
cout<<ca++<<endl<<endl;
init();
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;add(u,v);add(v,u);
}
solve();
cout<<'#'<<endl;
}
return 0;
}
|