tarjan算法入门

发表于   |   分类于

基本概念

关节点（割顶）：对于无向图G，如果删除某个点u后，连通分量数目增加，则称u为图的关节点
桥：若删除某条边e后，连通分量增加，则称e为图的桥
DFS森林中的边称为树边，第一次处理时从后代指向祖先的边称为反向边
深度优先序（时间戳）：dfs搜索过程中，按访问次序给顶点标记的编号

基本思想

在无向连通图G的DFS树中：
割顶
1）根结点u是G的割顶当且仅当u至少有两个子孩子
2）非根结点u是G的割顶当且仅当u存在一个子结点v,
使得v及其所有的后代都没有反向边连回到u的祖先(连回u不算)。
设dfn(u)为结点u的深度优先序，low(u)为u及其后代能连回的最早祖先的dfn值
若dfs搜索中u在v前先被访问，则dfn(u)=dfn(u)
桥
无向边(u,v)是图G的桥，当且仅当(u,v)为树边，且满足low(v)>dfn(u)
强连通分量SCC
从u的子结点出发,可以到达u的祖先w,则u,v,w在同一个SCC,则u不是该SCC第一个被发现的点
如果从v发现最多只能到u,那么u是该SCC中第一个被发现的点。即low(u)=dfn(u)时满足

HDU 1269 迷宫城堡

链接

迷宫城堡

题意

判断有向图G是否为强连通图

分析

求出强连通分量数，若个数大于1，则图G不是强连通图

参考代码

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
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
#define min(a,b) a<b?a:b
const int N=10010;
vector<int> G[N];
stack<int> S;
int n,m,dfs_clock,scc_cnt;
int dfn[N],low[N],sccno[N];
void init()
{
    for(int i=1;i<=n;i++)
        G[i].clear();
    while(!S.empty())
        S.pop();
    dfs_clock=1;
    scc_cnt=0;
    memset(dfn,0,sizeof(dfn));
    memset(sccno,0,sizeof(sccno));
}
void tarjan(int u)
{
    dfn[u]=low[u]=dfs_clock++;
    S.push(u);
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u]){
        while(!S.empty()){
            int x=S.top();
            S.pop();
            sccno[x]=scc_cnt;
            if(x==u)
                break;
        }
        scc_cnt++;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)
            break;
        init();
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i])
                tarjan(i);
        }
        if(scc_cnt>1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

HDU 1827 Summer Holiday

链接

Summer Holiday

题意

Wiskey有一个消息想告诉大家(N个人),他知道其他人也有一些别人的联系方式，
这样他可以通知其他人，再让其他人帮忙通知一下别人。已知M组联系关系，
问Wiskey至少要通知几个人才能使得所有人都被通知到？

分析

求强连通分量缩点后，计算有多少个入度为零的点(不能被其他人通知到)即为答案

参考代码

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
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
#define min(a,b) a<b?a:b
#define INF 99999999
const int N=1010;
vector<int> G[N];
stack<int> S;
int n,m,dfs_clock,scc_cnt,cost[N];
int dfn[N],low[N],sccno[N],minc[N];
void init()
{
    for(int i=1;i<=n;i++)
        G[i].clear();
    while(!S.empty())
        S.pop();
    dfs_clock=1;
    scc_cnt=0;
    memset(dfn,0,sizeof(dfn));
    memset(sccno,0,sizeof(sccno));
}
void tarjan(int u)
{
    dfn[u]=low[u]=dfs_clock++;
    S.push(u);
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u]){
        scc_cnt++;
        int tmp=INF;
        while(!S.empty()){
            int x=S.top();
            S.pop();
            sccno[x]=scc_cnt;
            tmp=min(tmp,cost[x]);
            if(x==u)
                break;
        }
        minc[scc_cnt]=tmp;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        for(int i=1;i<=n;i++)
            scanf("%d",&cost[i]);
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i])
                tarjan(i);
        }
        int rd[N]={0};
        for(int u=1;u<=n;u++){  //计算入度
            for(int i=0;i<(int)G[u].size();i++){
                int v=G[u][i];
                if(sccno[u]!=sccno[v])
                    rd[sccno[v]]++;
            }
        }
        int cnt=0,sum=0;
        for(int i=1;i<=scc_cnt;i++){
            if(!rd[i]){
                cnt++;
                sum+=minc[i];
            }
        }
        printf("%d %d\n",cnt,sum);
    }
    return 0;
}

POJ 1827 SPF

链接

SPF

题意

对于一个连通的网络，如果一个结点出现故障，将阻止至少一对结点之间的通信，
则该结点是SPF结点。给定一个网络，求有多少个SPF结点

分析

SPF点即为关节点，求有多少个关节点即可

参考代码

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
const int maxn=1010;
using namespace std;
int n,dfn_cnt,dfn[maxn],low[maxn],bcc[maxn];
vector<int> G[maxn];
void init()
{
    for(int i=0;i<maxn;i++)
        G[i].clear();
    n=0;
    dfn_cnt=1;
    memset(dfn,0,sizeof(dfn));
    memset(bcc,0,sizeof(bcc));
}
void tarjan(int u,int fa)
{
    int child=0;
    dfn[u]=low[u]=dfn_cnt++;
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if(!dfn[v]){
            child++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                if(fa!=0)
                    bcc[u]++;
            }
        }
        else if(dfn[v]<dfn[u]&&v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa==0&&child>1)
        bcc[u]=child-1;
}
int main()
{
    int u,v,T=1;
    while(scanf("%d",&u)!=EOF){
        if(u==0)
            break;
        init();
        while(scanf("%d",&v)!=EOF){
            G[u].push_back(v);
            G[v].push_back(u);
            n=max(n,u);
            n=max(n,v);
            scanf("%d",&u);
            if(u==0)
                break;
        }
        printf("Network #%d\n",T++);
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                tarjan(i,0);
            }
        }
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(bcc[i]>0){
                flag=true;
                printf("  SPF node %d leaves %d subnets\n",i,bcc[i]+1);
            }
        }
        if(!flag)
            printf("  No SPF nodes\n");
        printf("\n");
    }
    return 0;
}

链接

Popular Cows

题意

有N头牛，M组关系A B,表示A认为B更受欢迎。若A认为B更受欢迎，B认为C更受欢迎，
则A也认为C更受欢迎。求有多少头牛被其他所有(N-1头)牛认为更受欢迎

分析

先计算强连通分量缩点，再求有多少点的出度为0，若出度为0的点大于1，则答案为0，
否则答案为出度为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
85
86
87
88
#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
const int N=10010;
const int M=50010;
struct Edge{
    int to;
    int next;
}edge[M];
int head[N],edge_cnt,scc_cnt,dfn_cnt,top;
int dfn[N],low[N],sccno[N],num[N],od[N],Stack[N];
void init()
{
    dfn_cnt=1;
    edge_cnt=scc_cnt=top=0;
    memset(head,-1,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(sccno,0,sizeof(sccno));
    memset(num,0,sizeof(num));
}
void addEdge(int u,int v)
{
    edge[edge_cnt].to=v;
    edge[edge_cnt].next=head[u];
    head[u]=edge_cnt++;
}
void tarjan(int u)
{
    Stack[top++]=u;
    dfn[u]=low[u]=dfn_cnt++;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        scc_cnt++;
        while(top>=1){
            int x=Stack[top-1];
            top--;
            sccno[x]=scc_cnt;
            num[scc_cnt]++;
            if(x==u)
                break;
        }
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            addEdge(u,v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i])
                tarjan(i);
        }
        memset(od,0,sizeof(od));
        for(int u=1;u<=n;u++){
            for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].to;
                if(sccno[u]!=sccno[v])
                    od[sccno[u]]++;
            }
        }
        int cnt=0,pos=0;
        for(int i=1;i<=scc_cnt;i++){
            if(od[i]==0){
                pos=i;
                cnt++;
            }
        }
        if(cnt>1)
            printf("0\n");
        else
            printf("%d\n",num[pos]);
    }
    return 0;
}

POJ 2762 Going from u to v or from v to u?

链接

Going from u to v or from v to u?

题意

判断一个有向图是否为弱连通图

分析

求出强连通分量并缩点，记录每个点(连通分量)的入度，进行拓扑排序，
若每次仅存在一个入度为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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<stdio.h>
#include<string.h>
#include<vector>
#define min(a,b) a<b?a:b
using namespace std;
const int N=1010;
const int M=6010;
struct Edge{
    int to;
    int next;
}edge[M];
int top,dfn_cnt,scc_cnt,edge_cnt,rd[N];
int head[N],dfn[N],sccno[N],low[N],Stack[N];
bool vis[N],mark[N][N];
vector<int> G[N];
void init()
{
    top=0;
    dfn_cnt=1;
    scc_cnt=edge_cnt=0;
    memset(head,-1,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(sccno,0,sizeof(sccno));
    for(int i=0;i<N;i++)
        G[i].clear();
}
void addEdge(int u,int v)
{
    edge[edge_cnt].to=v;
    edge[edge_cnt].next=head[u];
    head[u]=edge_cnt++;
}
void tarjan(int u) //求强连通分量
{
    Stack[top++]=u;
    dfn[u]=low[u]=dfn_cnt++;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        scc_cnt++;
        while(top>0){
            int x=Stack[top-1];
            top--;
            sccno[x]=scc_cnt;
            if(x==u)
                break;
        }
    }
}
bool tpSort()  //拓扑排序
{
    for(int i=1;i<=scc_cnt;i++){
        int cnt=0,pos=-1;
        for(int j=1;j<=scc_cnt;j++){
            if(!vis[j]&&!rd[j]){
                cnt++;
                vis[j]=true;
                pos=j;
            }
        }
        if(cnt>1)
            return false;
        for(int j=0;j<(int)G[pos].size();j++){
            int v=G[pos][j];
            rd[v]--;
        }
    }
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            addEdge(u,v);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        edge_cnt=0;
        memset(rd,0,sizeof(rd));
        memset(vis,0,sizeof(vis));
        memset(mark,0,sizeof(mark));
        for(int u=1;u<=n;u++){
            for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].to;
                if(sccno[u]!=sccno[v]){
                    if(!mark[sccno[u]][sccno[v]]){
                        mark[sccno[u]][sccno[v]]=true;
                        G[sccno[u]].push_back(sccno[v]);
                        rd[sccno[v]]++;
                    }
                }
            }
        }
        bool flag=tpSort();
        if(!flag)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}