Tarjan_c#实现tarjan

作者：我家自动化 | 2024-02-06 21:35:34

踩

c#实现tarjan

有向图的强连通分量：

~~因为是复习，所以在此不进行算法赘述~~

算法介绍：https://www.cnblogs.com/mhpp/p/6751723.html

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

vector<int> g[1001];
stack<int> s;
int n,m,scc[1001],x,y,low[1001],dfn[1001],ind,sccNum[1001],sccV;

void tarjan(int u){
    low[u]=dfn[u]=++ind;
    s.push(u);
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(!scc[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(low[u]==dfn[u]){
        sccV++;
        int v;
        do{
            v=s.top();
            s.pop();
            scc[v]=sccV;
            sccNum[sccV]++;
        }while(u!=v);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        g[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        if(dfn[i]==0)tarjan(i);
    }
    for(int i=1;i<=n;i++){
        if(sccNum[scc[i]]>1)cout<<"T"<<endl;
        else cout<<"F"<<endl;
    }
}
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

时间复杂度：

O(n+m) n为点数,m为边数

割点与桥：

定义：

割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点称为割点
桥（割边）：无向连通图中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边

割点与桥（割边）的关系：

1）有割点不一定有桥,有桥一定存在割点

2）桥一定是割点依附的边。

下图中顶点C为割点，但和C相连的边都不是桥

判定方法：

ps: v为u的子节点

如果low[v] >= dfn[u]：
就说明 V 访问 U 的祖先顶点，必须通过 U ，所以 U 就是一个割点
如果low[v] > dfn[u]：
就说明 V-U 是桥（类似上文）

双连通图：

边双连通图：一个图无桥

构造方法：

首先按桥缩点，形成的图一定是一棵树，有桥。

然后统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。

则至少在树上添加(leaf+1)/2条边，就能使树达到双连通，所以至少添加的边数就是(leaf+1)/2。

具体方法：

在两个最近公共祖先最远的叶节点之间连接一条边，这样这两个点到祖先的路径加这条边就形成了一个环。

以此类推，恰好需要执行(leaf+1)/2次操作。
1
2
3
4
5
6
7
8
9
10
11

//按桥缩点 (leaf+1)/2= 添最少的边能使无向图变成双连通图
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct edge{
    int t,id;
};
vector<edge> g[5001];
stack<int> s;
int low[5001],dfn[5001],bcc[5001],deg[5001],bcc_num,n,m,x,y,ind,br,leaf;
bool net[5001][5001];
void tarjan(int u,int fa) {
    dfn[u]=low[u]=++ind;
    s.push(u);
    for(int i=0; i<g[u].size(); i++) {
        int v=g[u][i].t;
        if(!dfn[v]) {
            tarjan(v,g[u][i].id);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) {
                bcc_num++;
                br++;
                int k;
                do {
                    k=s.top();
                    s.pop();
                    bcc[k]=bcc_num;
                } while(k!=v);
            }
        } else {
            if(dfn[v]<dfn[u]&&fa/2!=g[u][i].id/2) {
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(fa==-1) {
        bcc_num++;
        while(!s.empty()) {
            int k=s.top();
            s.pop();
            bcc[k]=bcc_num;
        }
    }
}

int main() {
    cin>>n>>m;
    for(int i=0; i<m; i++) {
        cin>>x>>y;
        g[x].push_back((edge){y,i*2});
        g[y].push_back((edge){x,i*2+1});
    }
    for(int i=1; i<=n; i++) {
        if(!dfn[i])tarjan(i,-1);
    }
    for(int i=1; i<=n; i++) {
        for(int j=0; j<g[i].size(); j++) {
            int k=g[i][j].t;
            if(bcc[i]!=bcc[k]&&net[bcc[i]][bcc[k]]==false) {
                net[bcc[i]][bcc[k]]=true;
                net[bcc[k]][bcc[i]]=true;
                deg[bcc[i]]++;
                deg[bcc[k]]++;
            }
        }
    }
    for(int i=1; i<=bcc_num; i++) {
        if(deg[i]==1)leaf++;
    }
    cout<<br<<endl;
    cout<<(leaf+1)/2<<endl;
}
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

点双连通图：一个图无割点

//求割点及每个割点把图分成几部分 
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int> g[1001];
int dfn[1001],low[1001],cp[1001],n,s,t,ind,c=1;
bool flag;
void init(){
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(cp,0,sizeof(cp));
    for(int i=1;i<=1000;i++)g[i].clear();
    ind=0;
    flag=false;
    c++;
    n=0;
}

void tarjan(int u,int fa){
    dfn[u]=low[u]=++ind;
    int child=0;
    for(int i=0;i<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])cp[u]++;
        }else{
            if(dfn[v]<dfn[u]&&v!=fa){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(fa<0&&child==1)cp[u]=0;
}

void work(){
    if(flag==false)return;
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,-1);
    }
    cout<<"Network #"<<c<<endl;
    bool spf=false;
    for(int i=1;i<=n;i++){
        if(cp[i]!=0){
            if(i==1)cp[i]--;
            cout<<"  SPF node "<<i<<" leaves "<<cp[i]+1<<" subnets"<<endl;
            spf=true;
        }
    }
    if(spf==false){
        cout<<"  No SPF nodes"<<endl;
    }
    cout<<endl;
}

int main(){
    while(cin>>s){
        if(s==0){
            work();
            init();
            continue;   
        }
        cin>>t;
        flag=true;
        g[s].push_back(t);
        g[t].push_back(s);  
        n=max(n,s);
        n=max(n,t); 
    }
}
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

//找点双——栈里存点 
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=5e4+10;
const int M=3e5+10;
struct Edge{int v,nxt;}edge[M<<1];
int cnt,head[N],n,m;
int dfn[N],low[N],ind,s[N],top;
vector<int> dcc[N];int num;
void addedge(int u,int v){
	edge[++cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt;
}
void tarjan(int u,int fa){
	dfn[u]=low[u]=++ind;
	s[++top]=u;
	if(fa==-1&&!head[u]){//孤立点
        dcc[++num].push_back(u);
        return;
    }
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				num++;
				int x=0;
				do{
					x=s[top--];
					dcc[num].push_back(x); 
				}while(x!=v);
				dcc[num].push_back(u);//u加到点双里,但不出栈 
			}
		}
		else if(dfn[v]<dfn[u]&&v!=fa){
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,-1);
	for(int i=1;i<=num;i++){
		for(int j=0;j<dcc[i].size();j++) printf("%d ",dcc[i][j]);
		puts("");
	}
	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

//找点双——栈里存边
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=1010;
const int M=100010;
struct Edge{
	int u,v,nxt;
}edge[M<<2];
int n,m,cnt,head[N];
int ind,low[N],dfn[N],num,bn[N];
int s[M],top;
int no[N][N],odd[N],col[N];
vector<int> dcc[N];
void init(){
	memset(bn,0,sizeof(bn));
    memset(no,0,sizeof(no));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(odd,0,sizeof(odd));
    memset(head,0,sizeof(head));
    cnt=0,ind=0,num=0,top=0;
}
void addedge(int u,int v){
	edge[++cnt].u=u;edge[cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt;
}
void tarjan(int u,int fa){
    low[u]=dfn[u]=++ind;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(!dfn[v]){
            s[++top]=i;//先压栈再遍历
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                num++;
                dcc[num].clear();
                int x;
                do{
                	x=s[top--];
                	if(bn[edge[x].u]!=num){
                		dcc[num].push_back(edge[x].u);
						bn[edge[x].u]=num;
					}
                    if(bn[edge[x].v]!=num){
                    	dcc[num].push_back(edge[x].v);
						bn[edge[x].v]=num;
					}
				}while(x!=i);
            }
        }
        else if(dfn[v]<dfn[u]&&v!=fa){
            s[++top]=i; 
            low[u]=min(low[u],dfn[v]);
        }
    }
}
int dfs(int u,int k){
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(bn[v]!=k) continue;  
        if(col[v]==-1){  
            col[v]=col[u]^1;  
            if(!dfs(v,k)) return 0;
        }
        else if(col[v]==col[u]) return 0;
    }
    return 1;
}
int main(){
    while(1){
        init();
        scanf("%d%d",&n,&m);
        if(!n&&!m) break;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if(!x&&!y) break;
            no[x][y]=1;no[y][x]=1;
        }
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
                if(i==j||no[i][j]) continue;
                addedge(i,j);
            }
		}
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i,0);
        for(int i=1;i<=num;i++){
            for(int j=0;j<dcc[i].size();j++)
                col[dcc[i][j]]=-1,bn[dcc[i][j]]=i;
            col[dcc[i][0]]=1;
            if(!dfs(dcc[i][0],i)){
                for(int j=0;j<dcc[i].size();j++) odd[dcc[i][j]]=1;
            }
        }
        int ans=n;
        for(int i=1;i<=n;i++)
            if(odd[i]) ans--;
        cout<<ans<<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
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/64649