Tarjan算法与无向连通图（求割点与桥点、边双连通分量及其缩点）

前置知识点
- 桥：是存在于无向图中的这样的一条边，如果去掉这一条边，那么整张无向图会分为两部分，这样的一条边称为桥无向连通图中，如果删除某边后，图变成不连通，则称该边为桥。
- 无向连通图中，如果删除某点后，图变成不连通，则称该点为割点。
- 时间戳：dfs中按照每个结点第一次被访问的时间顺序，依次给予N个结点1~N的整数标记记为dfn[x]
- 搜索树：dfs过程中每个结点只访问一次，经过的边组成一颗搜索树
- 追溯值：设subtree(x)表示搜索树中以x为根的子树，low[x]定义为以下节点的时间戳的最小值
  - subtree(x)中的结点
  - 通过1条不在搜索树上的边，能够到达subtree(x)的结点
无向边(x,y)是桥，当且仅当

割边判定法则

dfn[x] < low[y]
代码

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int SIZE = 100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE*2],n,m,tot,num;
bool bridge[SIZE*2];

void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

void tarjan(int x, int in_edge){
	dfn[x] = low[x] = ++num;
	for(int i=head[x];i;i=Next[i]){
		int y = ver[i];
		if(!dfn[y]){
			tarjan(y,i);
			low[x] = min(low[x], low[y]);
			
			if(low[y] > dfn[x])
				bridge[i] = bridge[i ^ 1] = true;
		}
		else if(i != (in_edge^1)){ 
			low[x] = min(low[x], dfn[y]);
		}
	}
}

int main(){
	cin>>n>>m;
	CLR(head);
	CLR(low);
	CLR(dfn);
	CLR(bridge);
	num = 0;
	tot = 1;//2对应3... 
	rep(i,1,m){
		int x,y;
		scanf("%d%d", &x, &y);
		add(x,y),add(y,x);
	}
	rep(i,1,n){
		if(!dfn[i])tarjan(i,0);
	}
	for(int i=2;i<tot;i+=2){
		if(bridge[i])
			printf("%d %d\n", ver[i^1], ver[i]);
	}
	
	return 0;
}

割点判定法则

dfn[x] <= low[y]
代码

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int SIZE = 100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE*2],n,m,tot,num,root;
bool cut[SIZE*2];

void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

void tarjan(int x){
	dfn[x] = low[x] = ++num;
	int flag = 0;
	for(int i=head[x];i;i=Next[i]){
		int y = ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x] = min(low[x], low[y]);
			
			if(low[y] >= dfn[x]){
				++flag;
				if(x!=root||flag>1)cut[i]=true;
			}
		}
		else{ 
			low[x] = min(low[x], dfn[y]);
		}
	}
}

int main(){
	cin>>n>>m;
	CLR(head);
	CLR(low);
	CLR(dfn);
	CLR(cut);
	num = 0;
	tot = 1;//2对应3... 
	rep(i,1,m){
		int x,y;
		scanf("%d%d", &x, &y);
		if(x==y)continue;
		add(x,y),add(y,x);
	}
	rep(i,1,n){
		if(!dfn[i])root=i,tarjan(i);
	}
	for(int i=2;i<tot;i+=2){
		if(cut[i]) printf("%d ", i);
	}
	puts("are cut-vertexes");
	
	return 0;
}

边连通分量（e-DCC）

定义：没有桥的无向连通图

求e-DCC

c[x]表示节点x所属的“边连通分量”的编号，dcc表示分量的块数
1. 先用tarjan算法标记出所有的桥边
2. 再对整个无向图执行一次dfs，划分出每个连通块
代码

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int SIZE = 100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE*2],n,m,tot,num;
bool bridge[SIZE*2];


void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

void tarjan(int x, int in_edge){
	dfn[x] = low[x] = ++num;
	for(int i=head[x];i;i=Next[i]){
		int y = ver[i];
		if(!dfn[y]){
			tarjan(y,i);
			low[x] = min(low[x], low[y]);
			
			if(low[y] > dfn[x])
				bridge[i] = bridge[i ^ 1] = true;
		}
		else if(i != (in_edge^1)){ 
			low[x] = min(low[x], dfn[y]);
		}
	}
}

int c[SIZE],dcc;
void dfs(int x){
	c[x] =dcc;
	for(int i=head[x];i;i=Next[i]){
		int y = ver[i];
		if(c[y] || bridge[i])continue;
		dfs(y);
	}
}

int main(){
	cin>>n>>m;
	CLR(head);
	CLR(low);
	CLR(dfn);
	CLR(bridge);
	CLR(c);		
	num = 0;
	tot = 1;//2对应3... 
	dcc = 0;
	rep(i,1,m){
		int x,y;
		scanf("%d%d", &x, &y);
		add(x,y),add(y,x);
	}
	rep(i,1,n){
		if(!dfn[i])tarjan(i,0);
	}
	for(int i=2;i<tot;i+=2){
		if(bridge[i])
			printf("%d %d\n", ver[i^1], ver[i]);
	}
	
	//求边连通分量
	rep(i,1,n){
		if(!c[i]){
			++dcc;
			dfs(i);
		}
	}
	printf("There ans %d e-DCC.\n", dcc);
	rep(i,1,n){
		printf("%d belongs to DCC %d.\n", i , c[i]);
	}
	return 0;
}

e-DCC缩点

代码建立在Tarjan求桥、求e-DCC的基础之上

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int SIZE = 100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE*2],n,m,tot,num;
bool bridge[SIZE*2];


void add(int x,int y) {
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

//求割边
void tarjan(int x, int in_edge) {
	dfn[x] = low[x] = ++num;
	for(int i=head[x]; i; i=Next[i]) {
		int y = ver[i];
		if(!dfn[y]) {
			tarjan(y,i);
			low[x] = min(low[x], low[y]);

			if(low[y] > dfn[x])
				bridge[i] = bridge[i ^ 1] = true;
		} else if(i != (in_edge^1)) {
			low[x] = min(low[x], dfn[y]);
		}
	}
}

//求e-DCC
int c[SIZE],dcc;
void dfs(int x) {
	c[x] =dcc;
	for(int i=head[x]; i; i=Next[i]) {
		int y = ver[i];
		if(c[y] || bridge[i])continue;
		dfs(y);
	}
}

//求e-DCC的缩点
int hc[SIZE], vc[SIZE*2],nc[SIZE*2] ,tc;
void add_c(int x,int y) {
	vc[++tc] = y;
	nc[tc] = hc[x];
	hc[x] = tc;
}

int main() {
	cin>>n>>m;
	CLR(head);
	CLR(low);
	CLR(dfn);
	CLR(bridge);
	
	num = 0;
	tot = 1;//2对应3...

	rep(i,1,m) {
		int x,y;
		scanf("%d%d", &x, &y);
		add(x,y),add(y,x);
	}
	rep(i,1,n) {
		if(!dfn[i])tarjan(i,0);
	}
	for(int i=2; i<tot; i+=2) {
		if(bridge[i])
			printf("%d %d\n", ver[i^1], ver[i]);
	}


	//求e-DCC
	CLR(c);
	dcc = 0;
	rep(i,1,n) {
		if(!c[i]) {
			++dcc;
			dfs(i);
		}
	}
	printf("There ans %d e-DCC.\n", dcc);
	rep(i,1,n) {
		printf("%d belongs to DCC %d.\n", i , c[i]);
	}

	//求e-DCC的缩点
	CLR(hc);
	tc=1;
	
	rep(i,2,tot){
		int x = ver[i^1],y=ver[i];
		if(c[x] == c[y]) continue;
		add_c(c[x], c[y]);
	}
	printf("缩点之后的森林，点数%d，边数%d（可能有重边）\n", dcc,tc/2);
	for(int i=2;i<tc;i+=2){//i<=tc | i<tc 都行 
		printf("%d %d\n", vc[i^1], vc[i]); 
	}
	return 0;
}

点连通分量（v-DCC）

定义：没有割点的无向连通图（割点可以属于多个v-DCC）

求v-DCC

我们需要维护一个栈，并按如下方法维护栈中的元素
1. 当一个结点第一次被访问时，把该结点入栈
2. 当割点判定法则中的条件dfn[x]<=low[y]成立时，无论x是否为根，都要
3. 从栈顶不断地弹出结点，直至结点y被弹出，刚才弹出的所有结点与结点x一起构成一个v-DCC
dcc[i]保存编号为i的v-DCC中的所有结点
代码

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int SIZE = 100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE*2],n,m,tot,num,root;
bool cut[SIZE*2];

void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

vector<int>dcc[SIZE];
int cnt, top;
int Stack[SIZE];

void tarjan(int x){
	dfn[x] = low[x] = ++num;
	Stack[++top] = x;
	if(x == root && head[x] == 0){ // 孤立点 
		dcc[++cnt].push_back(x);
		return; 
	}
	int flag = 0;
	for(int i=head[x];i;i=Next[i]){
		int y = ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if(low[y] >= dfn[x]){
				++flag;
				if(x!=root||flag>1)cut[x]=true;
				
				++cnt;
				int z;
				do{
					z = Stack[top--];
					dcc[cnt].push_back(z);
				}while(z != y);
				dcc[cnt].push_back(x);
			}
		}
		else{ 
			low[x] = min(low[x], dfn[y]);
		}
	}
}

int main(){
	cin>>n>>m;
	CLR(head);
	CLR(low);
	CLR(dfn);
	CLR(cut);
	num = 0;
	tot = 1;//2对应3... 
	
	cnt = 0, top = 0;
	for(int i=0;i<SIZE;++i) dcc[i].clear();
	
	rep(i,1,m){
		int x,y;
		scanf("%d%d", &x, &y);
		if(x==y)continue;
		add(x,y),add(y,x);
	}
	rep(i,1,n){
		if(!dfn[i])root=i,tarjan(i);
	}
	for(int i=2;i<tot;i+=2){
		if(cut[i]) printf("%d ", i);
	}
	puts("are cut-vertexes");
	
	
	rep(i,1,cnt){
		printf("v-DCC #%d:", i);
		for(int j=0;j<dcc[i].size();++j){
			printf(" %d", dcc[i][j]);
		}
		puts("");
	}
	return 0;
}

v-DCC的缩点

设图中共有p个割点和t个v-DCC
1. 建立一张包含p+t个结点的新图
2. 把每个v-DCC和每个割点都作为新图中的结点
3. 在每个割点与包含它的所有v-DCC之间连边
代码建立在Tarjan求割点、求v-DCC的基础之上

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int SIZE = 100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE*2],n,m,tot,num,root;
bool cut[SIZE*2];

void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

vector<int>dcc[SIZE];
int cnt, top;
int Stack[SIZE];


//tarjan求割点、求v-DCC 
void tarjan(int x){
	dfn[x] = low[x] = ++num;
	Stack[++top] = x;
	if(x == root && head[x] == 0){ // 孤立点 
		dcc[++cnt].push_back(x);
		return; 
	}
	int flag = 0;
	for(int i=head[x];i;i=Next[i]){
		int y = ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if(low[y] >= dfn[x]){
				++flag;
				if(x!=root||flag>1)cut[x]=true;
				
				++cnt;
				int z;
				do{
					z = Stack[top--];
					dcc[cnt].push_back(z);
				}while(z != y);
				dcc[cnt].push_back(x);
			}
		}
		else{ 
			low[x] = min(low[x], dfn[y]);
		}
	}
}

//求v-DCC的缩点 
int new_id[SIZE], c[SIZE];
int hc[SIZE], vc[SIZE*2],nc[SIZE*2] ,tc;
void add_c(int x,int y) {
	vc[++tc] = y;
	nc[tc] = hc[x];
	hc[x] = tc;
}

int main(){
	cin>>n>>m;
	CLR(head);
	CLR(low);
	CLR(dfn);
	CLR(cut);
	tot = 1;//2对应3... 
	num = 0;
	
	
	
	//求割点 
	rep(i,1,m){
		int x,y;
		scanf("%d%d", &x, &y);
		if(x==y)continue;
		add(x,y),add(y,x);
	}
	rep(i,1,n){
		if(!dfn[i])root=i,tarjan(i);
	}
	for(int i=2;i<tot;i+=2){
		if(cut[i]) printf("%d ", i);
	}
	puts("are cut-vertexes");
	
	//求v-DCC
	cnt = 0, top = 0;
	for(int i=0;i<SIZE;++i) dcc[i].clear();
	rep(i,1,cnt){
		printf("v-DCC #%d:", i);
		for(int j=0;j<dcc[i].size();++j){
			printf(" %d", dcc[i][j]);
		}
		puts("");
	}
	
	//求v-DCC的缩点
	CLR(new_id);
	CLR(hc);
	CLR(c);
	tc = 1; 
	num = cnt;//给每个割点一个新的编号，从cnt+1开始 
	rep(i,1,n)
		if(cut[i]) new_id[i] = ++num;
	rep(i,1,cnt){
		for(int j=0;j<dcc[i].size();++j){
			int x = dcc[i][j];
			if(cut[x]){
				add_c(i,new_id[x]);
				add_c(new_id[x],i);
			}else{
				c[x] = i;//除割点外，其他点仅属于一个v-DCC 
			}
		}
	}
	printf("缩点之后的森林，点数%d，边数%d\n", num, tc/2);
	printf("编号 1~%d 的为原图的 v-DCC，编号 >%d 的为原图割点\n", cnt,cnt);
	for(int i=2;i<tc;i+=2){
		printf("%d %d\n", vc[i^1], vc[i]);
	} 
	return 0;
}

发表评论 取消回复

发表评论取消回复