soj 1075 拓扑排序队列实现

就是soj 拓扑排序的模板题吧。然后我中午把用队列实现的拓扑排序的方法看了下。晚上就打算来练一下这种纯模板。

对于这实现的方法，我的理解就是存下每个节点的入度以及它指向的其他节点，由于指向多少个这个不太能确定所以用一个vector来存。然后将入度为零的节点取出来入队列，再将其所指向的节点之间的边都删掉（也就是将所指向的节点的入度减1）减掉之后如果这个点变为入度为0了，就可以将其入队了。。还有关于输出的问题就是每次从队列中取出一个出来，那么这个就是此时的节点，就可以将它输出了。

大概就是这样的吧，我也不知道自己理解错了没有。

给个别人写的拓扑排序的原理及实现吧，http://www.2cto.com/kf/201308/233520.html

对于这道题来说：题目中指明了每个输入只有对应一种输出，并且不可能没有输出，所以我们连判断有没有环都不需要了。

背景：我一开始写错了，连没有输入的字母都出现了，后来加了个数组用于标记这个字母是否出现才解决了这个问题。还有就是要注意格式的控制，而且对于每一个vector都要进行初始化。其他应该没有什么了毕竟第一道拓扑排序，就是模板题啊。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define M 100
int s[M];  //来记录每个字母的入度
vector<int> G[M];  //用vector来存储当前这个点所指向的各个点
int mark[M];      //标记这个字母是否在输入之中
int n;
void topo()
{
    queue<int> q;
    int first = 1;
    for(int i = 0;i < 26;i++)
        if(!s[i]&&mark[i])
        q.push(i);
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        if(first) printf("%c",t+'A');   //如果是第一次就不需要前面的空格
        else printf(" %c",t+'A');
        first = 0;
        for(int i = 0;i < G[t].size();i++)
        {
            s[G[t][i]]--;
            if(s[G[t][i]]==0)
                q.push(G[t][i]);
        }
    }
}
int main()
{
    while(scanf("%d",&n)==1 && n)
    {
        memset(mark,0,sizeof(mark));
        for(int i = 0;i < 26;i++)
            G[i].clear();  //要对每一个vector进行初始化，不然不同组之间会相互影响
        for(int i = 0;i < n;i++)
        {
            char a,b;
            cin >> a >> b;
            mark[a-'A'] = 1;
            mark[b-'A'] = 1;
            s[b-'A']++;
            G[a-'A'].push_back(b-'A');
        }
        topo();
        printf("\n");
    }
    return 0;
}