トポロジーソート//SDNUOJ 1089

1行目--グーグー.
やっぱりグーグーで止まらないブロガーです.
 
トポロジのソート:
1.有向無環図に適用する.すなわち、後に現れるノードが前のノードを指していない.
2.本質的には、図中のノードをソートする.入度ゼロでソートします.入力がゼロの点が存在しない場合はループがあり、トポロジーソートは存在しません.
3.意味:実は私も何の役に立つか分かりません.優先順位が存在するので、ソート(??)に使用できます.
4.あ!思い出しました.データ構造で授業の問題を解決するために使われています.大学1年生がc言語を大きくしてからデータ構造を学ぶことができるように、cはデータ構造の先導授業だからだ.
5.サンプルコードは複雑度が高く、隣接テーブルで図を保存することができ、時間複雑度が低い.
6.キューで最適化することもできます.(さすがにこのO(n^2)は基本的に1 e^3以上ではダメです
7.いくつかの問題がソートされる必要があることを考慮すると(例えば、辞書順に出力され、6に基づいて優先キューを使用することができる.
 
このコードはSDNU 1089を例にとって、よく理解できるが時間の複雑さが高いコードOである(n^2)

#include 
#include 
#include 
#include 
#include 
#define ll long long

using namespace std;

int a[1001][1001] = {0};

int main()
{
    int n,m;
    int b[1001] = {0};
    int v[1001];
    bool vis[1001] = {0};
    int tot = 0;
    int f = 0;
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; ++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y] = 1;// x->y  
        b[y]++;//y   ++
    }
    for(int i = 1; i <= n; ++i)
    {
        int flag = 0;
        for(int j = 1; j <= n; ++j)
        {
            if(b[j] == 0&&!vis[j])
            {
                flag = 1;
                v[tot++] = j;
                vis[j] = 1;
                break;
            }
        }
        for(int j = 1; j <= n; ++j)
        {
            if(a[v[tot-1]][j] == 1)
            {
                b[j]--;
                a[v[tot-1]][j] = 0;
            }
        }
        if(flag == 0)
        {
            printf("IMPOSABLE
");
            f = 1;
            break;
        }
    }
    if(!f)
        for(int i = 0; i < tot; ++i)
        {
            if(i == 0)
                printf("%d",v[i]);
            else
                printf(" %d",v[i]);
        }
    return 0;
}

 
補足練習:
その他のトポロジーソート練習問題
これは偶然見つけた練習問題のリストです!中の問題は私が1つやったことがありますが!後続は補います!
OpenJ_Bailian-4084
HDU1285
上記の例のコードとは異なり、この2つの問題はエッジの問題を考慮しなければならない.(私はもう何度も穴をあけられました.
SDNUOJ1031
これは毎回並べ替えが必要で、私は何度もwaして、添付したのは問題解のブログで、中にテーマのリンクがあります.