템 플 릿 만 들 기토폴로지 정렬

/*author: Vit;
 *from: http://blog.csdn.net/svitter
 *if you like it , please show the origin site*/

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

struct Arc
{
    int point;
    int next;
};

Arc arc[50005];
int node[5005];
int digree[5005]; //   
int top[5005];

void Topsort()
{
    int n, m;
    scanf("%d%d", &n, &m);//edge = m, vertice = n;
    queue<int>q;
    for(int i = 1; i <= m; i++)
    {
        int a,b;
        scanf("%d%d", &a, &b);//

        arc[i].next = node[a];  //next_arc
        arc[i].point = b;       //  
        node[a] = i;            //   
        digree[b]++;            //  ++
    }

    for(int i = 1; i <= n; i++)
    {
        if(digree[i] == 0)
            q.push(i);
    }

    int l = 0;
    while(!q.empty())
    {
        int x = q.front();
        top[l++] = x;
        q.pop();
        for(int e = node[x]; e != -1; e = arc[e].next)
        {
            digree[arc[e].point]--;
            if(!digree[arc[e].point] == 0)
                q.push(arc[e].point);
        }
    }
}

int main()
{
    Topsort();
    return 0;
}

//============================================================================
// Name        :     .cpp
// Author      : vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define MAXV 50

/*
 *ANode       ，VNode      
 *count   ，adjvex        
 */
typedef struct ANode{

	//InfoType info;     
	int adjvex;//   
	struct ANode *nextarc;
}ArcNode;


typedef struct{
	//Vertex data;     
	int value;
	int count;	//  
	ArcNode *firstarc;
}VNode;

typedef VNode AdjList[MAXV];

typedef struct{
	AdjList adjlist;
	int n, e;//n   ，e   
}ALGraph;

void TopSort(ALGraph * G){
	int i, j;
	int St[MAXV];
	int top = -1;// 
	ArcNode *p;

	//     
	for(i = 0; i <= G->n; i++)
		G->adjlist[i].count = 0;
	//    

	for(i = 0; i <= G->n; i++){
		p = G->adjlist[i].firstarc;
		while(p != NULL){
			G->adjlist[p->adjvex].count++;
			p = p -> nextarc;
		}
	}
	//     0,   
	for(i = 0;  i<= G -> n; i ++){
		if(G->adjlist[i].count == 0){
			top ++;
			St[top] = i;
		}
	}

	for(i = 0; i <= G -> n; i++){
		printf("%d:%d
", i, G->adjlist[i].count);
	}
	printf("
");

	while(top >-1){
		i = St[top], top--;
		printf("%d", i);
		p = G -> adjlist[i].firstarc;
		//         -1
		while(p != NULL){
			j = p -> adjvex;
			G -> adjlist[j].count--;
			if( G-> adjlist[j].count == 0){//    ，  
				top++;
				St[top] = j;
			}
			p = p -> nextarc;//  
		}
	}
}

int visited[50];
void DFS(ALGraph * G, int v){//      ，    
	ArcNode * p;
	visited[v] = 1;
	printf("%d",v);
	p = G -> adjlist[v].firstarc;
	while(p != NULL){
		if(visited[p->adjvex] == 0)
			DFS(G, p -> adjvex);
		p = p -> nextarc;
	}
}

int main() {
	int i, m, n;
	int temp;
	ANode * t, * t2;
	ALGraph * G;
	memset(visited, 0, sizeof(visited));
	while (cin >> n >> m){
		G = new ALGraph();
		G->n = n;
		for(i = 1;  i <= n; i++){
			scanf("%d %d", &temp, &G->adjlist[i].value);
			if(G->adjlist[temp].firstarc == NULL){

				t = new ANode();
				G->adjlist[temp].firstarc = t;

				t->adjvex = i;
				t->nextarc = NULL;
			}
			else{
				t = G->adjlist[temp].firstarc;

				while(t->nextarc != NULL)
					t = t -> nextarc;

				t2 = new ANode();
				t -> nextarc = t2;
				t2 -> adjvex = i;
				t2 -> nextarc = NULL;
			}
		}

		printf("check
");//     
		for(i = 0;  i <= n; i++){
			printf("%d",i);
			t = G->adjlist[i].firstarc;
			if(t == NULL){
				printf("
");
				continue;
			}
			else{
				while(t != NULL){
					printf("->%d", t->adjvex);
					t = t->nextarc;
				}
			}
			printf("
");
		}

		printf("TopSort:
");
		TopSort(G);
	}


	return 0;
}