《输出图的连通分量算法实现》由会员分享，可在线阅读，更多相关《输出图的连通分量算法实现（3页珍藏版）》请在金锄头文库上搜索。
1、/输出图的连通分量算法实现#include #include #define MAXN 20/顶点数的最大值#define MAXM 40/边数的最大值#define min(a,b) (a)(b)?(b):(a)struct edgeint u, v;/边的两个顶点void output( ) printf( %d-%d, u, v ); int comp( edge& t ) return ( (u=t.u & v=t.v) | (u=t.v & v=t.u) );edge edgesMAXM;/边的数组（模拟栈）int se;/栈顶int EdgeMAXNMAXN;/邻接矩阵(1表示有连
2、接,2表示有连接且已经走过,0表示没有连接)int visitedMAXN;/表示顶点访问状态int n, m;/顶点数、边数int tmpdfn;/在dfs过程中记录当前的深度优先搜索序数int dfnMAXN;/每个顶点的dfn值int lowMAXN;/每个顶点的low值，根据该值来判断是否时关节点/深度优先搜索，记录每个节点的low值（根据low值来判断是否求关节点）void dfs( int u )for( int v=1; v= dfnu )/删除顶点u，子女节点v所在的子树将脱离bool firstedge = true;/控制最后一条边后面没有空格的状态变量while( 1 )
3、if( se0 ) break;if( firstedge ) firstedge = false;else printf( );edge t1;t1 = edgesse;t1.output( );/输出栈顶节点t1edgesse.u = 0; edgesse.v = 0;/删除栈顶t1se-;if( p(t) ) break;printf( n );/此前v已经访问过了，v是u的祖先节点（(v,u)就是一条回边）：情形else lowu = min(lowu, dfnv);int main( )int i;/循环变量int u, v;/从输入文件中读入的顶点对int number = 1;
4、/测试数据数目freopen( data.txt, r, stdin );freopen( out.txt, w, stdout );while( 1 )scanf( %d%d, &n, &m );if( n=0 & m=0 ) break;/整个输入结束memset( Edge, 0, sizeof(Edge) );for( i=1; i1 ) printf( n );/保证最后一个网络的输出之后没有空行number+;low1 = dfn1 = 1;tmpdfn = 1;memset( visited, 0, sizeof(visited) ); visited1 = 1;memset( edges, 0, sizeof(edges) );se = -1;dfs( 1 );/从顶点1出发进行DFS搜索return 0;代码转载注明http:/
