6-10 Strongly Connected Components(30分)

//ReadG()   ：
//1.      （    ）
//2.        

//ReadG()   ：
//1.          //   
//2.                 //       

//ReadG()  ：
//1.PtrToVNode *Array   PtrToVNode Next        ？
/*
            
             ：
    typedef struct VNode *PtrToVNode;
    struct VNode {
        Vertex Vert;
        PtrToVNode Next;
    };
    typedef struct GNode *Graph;
    struct GNode {
        int NumOfVertices;
        int NumOfEdges;
        PtrToVNode *Array;
    };//        
          ：
    1.
    Graph graph = (Graph)malloc(sizeof(struct GNode));

    2.     Array              ，
    graph->Array =
        (PtrToVNode *)malloc(graph->NumOfVertices * sizeof(PtrToVNode));
    3.        Array[i]         struct VNode   
    for(i = 0; i < graph->NumOfVertices; ++i)
        graph->Array[i] =
            (PtrToVNode)malloc(graph->NumOfVertices * sizeof(struct VNode));
    4.      NumOfVertices * NumOfVertices      
*/
//2.   （         ）     ？
/*
       Sample Input   ，
            
    5 -2
       5      //               （      -2）
*/

//StronglyConnectedComponents        Tarjan  
//              15     MaxVertices
//

#include 
#include 
//              15     MaxVertices
#define MaxVertices 10  /* maximum number of vertices */
typedef int Vertex;     /* vertices are numbered from 0 to MaxVertices-1 */
typedef struct VNode *PtrToVNode;
struct VNode {
    Vertex Vert;
    PtrToVNode Next;
};
typedef struct GNode *Graph;
struct GNode {
    int NumOfVertices;
    int NumOfEdges;
    PtrToVNode *Array;
};
Graph ReadG(); /* details omitted */

void PrintV( Vertex V )
{
   printf("%d ", V);
}

void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) );

int main()
{
    Graph G = ReadG();
    StronglyConnectedComponents( G, PrintV );
    return 0;
}

/* Your function will be put here */
void Insert(int a[], int *size, int x)//   ReadG()
{
    int i, j;
    for(i = 0; i < (*size); ++i){
        if(a[i] == x) return;
    }
    ++(*size);
    a[(*size)-1] = x;
}

Graph ReadG()
{
    Graph graph = (Graph)malloc(sizeof(struct GNode));

    scanf("%d %d", &(graph->NumOfVertices), &(graph->NumOfEdges));

    if(graph->NumOfVertices > 15){//15             
        return NULL;
    }

    graph->Array =
        (PtrToVNode *)malloc(graph->NumOfVertices * sizeof(PtrToVNode));

    int i;
    for(i = 0; i < graph->NumOfVertices; ++i)
    graph->Array[i] =
        (PtrToVNode)malloc(graph->NumOfVertices * sizeof(struct VNode));
        //Essential !!!

    for(i = 0; i < graph->NumOfVertices; ++i)
    {
        graph->Array[i]->Vert = -10;//
        graph->Array[i]->Next = NULL;
    }


    if(graph->NumOfEdges == 0 && graph->NumOfVertices > 0)//     ，        
    {
        for(i = 0; i < graph->NumOfVertices; ++i)
        {
            graph->Array[i]->Vert = i;
        }
        return graph;
    }


    int u, v;
    PtrToVNode current, //           ，        graph->Array[j]
                output;
    int vert_cnt = 0;//graph->Array[j]->Vert   （     ）
    int j = 0;
    int *a = (int *)malloc(graph->NumOfVertices * sizeof(int));//        （a[i]   ），                      
    int len_a = 0;//a     
    for(i = 0; i < graph->NumOfVertices; ++i) a[i] = -8;
    for(i = 0; i < graph->NumOfEdges; ++i)
    {
        scanf("%d %d", &u, &v);
        if(v == -2){//isolated point
            graph->Array[i]->Vert = u;
            graph->Array[i]->Next = NULL;//      ，    
            ++vert_cnt;
            ++i;
            continue;
        }
        current = (PtrToVNode)malloc(sizeof(struct VNode));
        for(j = 0; j < vert_cnt; ++j)
        {
            if(u == graph->Array[j]->Vert)
            {
                break;
            }
            else continue;
        }
        if(j == vert_cnt)
        {
            graph->Array[j]->Vert = u;
            ++vert_cnt;
        }
        current->Vert = v;
        current->Next = graph->Array[j]->Next;
        graph->Array[j]->Next = current;
        Insert(a, &len_a, v);
    }
    printf("print a[]
");
    for(i = 0; i < len_a; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("
then initialize the remanent point
");
    //then initialize the remanent point whose outdegree = 0 and indegree > 0
    //    a[]     Array[]               ，   Array[]  
    int discovered;
    for(i = 0; i < len_a; ++i)
    {
        discovered = 0;
        for(j = 0; j < vert_cnt; ++j)
        {
            if(a[i] == graph->Array[j]->Vert)
            {
                discovered = 1;
                break;
            }
        }
        if(discovered == 0)
        {
            graph->Array[vert_cnt]->Vert = a[i];
            //graph->Array[j]->Next = NULL;
            ++vert_cnt;
        }
    }
    printf("Input finished.Then try to output the input.
");
    for(i = 0; i < graph->NumOfVertices; ++i)
    {
        PrintV(graph->Array[i]->Vert);
        output = graph->Array[i]->Next;
        while(output != NULL)
        {
            PrintV(output->Vert);
            output = output->Next;
        }
        if(output == NULL)
            printf("
");
    }
    printf("READG() finished.
");
    return graph;
}

//             15 ，   MaxVertices==10
#define MaxInput 15
Vertex DFN[MaxInput] = {0},
//DFN［］            （   ），               。％           ％。
           LOW[MaxInput] = {0},
//           ，       ，      ，like              。      LOW［］  ，           ，               。
//ps：        ，   LOW［］＝DFN［］
           stack[MaxInput] = {0},
           access[MaxInput] = {0},
           cnt = 0, tot = 0, index = 0;
int min(int x, int y)
{
    return (xNumOfVertices; ++i)
    {
        if(g->Array[i]->Vert == x)
        {
            for(p = g->Array[i]->Next; p != NULL; p = p->Next)
            {
                if(!DFN[p->Vert]){
                    Tarjan(g, p->Vert, PrintV);
                    LOW[x] = min(LOW[x], LOW[p->Vert]);
                }
                else if(access[p->Vert]){
                    LOW[x] = min(LOW[x], DFN[p->Vert]);
                }
            }
            break;
        }

    }
    if(LOW[x] == DFN[x])
    {
        do{
            PrintV(stack[index]);
            access[stack[index]] = 0;
            index--;
            ++cnt;
        }while(x != stack[index+1]);
        if(cnt != g->NumOfVertices)
            printf("
");
    }
}
void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) )
{
    for(int i = 0; i < G->NumOfVertices; ++i)
        if(DFN[G->Array[i]->Vert]==0) Tarjan(G, G->Array[i]->Vert, PrintV);
}