#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define INFINIT 65535
typedef struct _ArcCell{
int adj; // Weight or flag about connection
int *info; // Other information
}ArcCell;
typedef char VertexType;
typedef enum{
DG,
DN,
UDG,
UDN
}GraphKind;
typedef struct _MGraph{
VertexType vexs[MAX];
ArcCell arcs[MAX][MAX];
int vexnum;
int arcnum;
GraphKind kind;
}MGraph;
int visited[MAX];
int low[MAX];
int count;
int LocateVex(MGraph *G, VertexType v)
{
int i=0;
while(i<G->vexnum && G->vexs[i] != v){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
int CreateUDG(MGraph *G)
{
int i,j,k;
char v1,v2;
scanf(" %d %d", &G->vexnum, &G->arcnum);
for(i=0; i<G->vexnum; i++){
scanf(" %c", &G->vexs[i] );
}
for(i=0; i<G->vexnum; i++){
for(j=0; j<G->vexnum; j++){
G->arcs[i][j].adj = INFINIT;
}
}
for(k=0; k<G->arcnum; k++){
scanf(" %c %c", &v1, &v2);
i=LocateVex(G, v1);
j=LocateVex(G, v2);
G->arcs[i][j].adj = 1;
G->arcs[j][i].adj = 1;
}
return 1;
}
int FirstAdjvex(MGraph *G, int v)
{
int i=0;
while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
int NextAdjvex(MGraph *G, int v, int w)
{
int i=w+1;
while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
void DFSArticul(MGraph *G, int v)
{
int w;
int min;
visited[v] = min = ++count;
for(w = FirstAdjvex(G, v); w>=0; w = NextAdjvex(G, v, w) ){
if(visited[w] == 0){
DFSArticul(G, w);
if(low[w] < min){
min = low[w];
}
if(low[w] >= visited[v]){
printf(" Articulation: %c (%d)\n", G->vexs[v], v);
}
}else if(visited[w] < min){
min = visited[w];
}
}
low[v] = min;
}
void FindArticul(MGraph *G)
{
int i;
int v;
int w;
count = 1;
visited[0] = 1;
low[0] = INFINIT;
for(i=1; i<G->vexnum; i++){
visited[i] = 0;
low[i] = INFINIT;
}
v = FirstAdjvex(G, 0);
DFSArticul(G, v);
if(count < G->vexnum){
printf(" Articulation: %c (%d)\n", G->vexs[0], 0);
for(w = NextAdjvex(G, 0, v); w>=0; w= NextAdjvex(G, 0, w) ){
if(visited[i] == 0){
DFSArticul(G, w);
}
}
}
printf(" The value of visited and low\n");
for(i=0; i<G->vexnum; i++){
printf(" %5d", i);
}
printf("\n");
for(i=0; i<G->vexnum; i++){
printf(" %c", G->vexs[i]);
}
printf("\n");
for(i=0; i<G->vexnum; i++){
printf(" %5d", visited[i]);
}
printf("\n");
for(i=0; i<G->vexnum; i++){
printf(" %5d", low[i]);
}
printf("\n");
}
void main()
{
MGraph G;
printf("log.anycle.com\n\n");
printf("Create graph:\n");
CreateUDG(&G);
printf("\n");
printf("Find articulation:\n");
FindArticul(&G);
printf("\n");
}