kuangbin专题拓扑排序

HDU1285 确定比赛名次思路

简单拓扑排序模板
注意：答案不唯一，输出字典序小的
我这里用的是小根堆维护

代码

#include
#include
#include
#include

using namespace std;

priority_queue, greater > heap;

const int N = 510, M = N * 2;
int q[N];
int h[N], ne[M], e[M], idx;
// 入度
int din[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        memset(h, -1, sizeof h);
        idx = 0;
        memset(din, 0, sizeof din);
        while(heap.size())
            heap.pop();

        while(m --) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            din[b]++;
        }

        for (int i = 1; i <= n; i ++)
            if(!din[i])
                heap.push(i);
        bool flag = false; // 输出空格处理
        while(heap.size()) {
            int t = heap.top();
            if(!flag) {
                printf("%d", t);
                flag = true;
            }
            else printf(" %d", t);
            heap.pop();
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if(-- din[j] == 0)
                    heap.push(j);
            }
        }  
        printf("n");
    }
}

HDU - 2647 Reward 思路

简单的差分约束，因为边权是正权，用拓扑序列即可。
建图：若A>B, 则A>=B + 1, 即B向A连一条权值为1的边。
题目取最小值，用最长路。

为什么取最小选择最长路呢，举个例子就知道了
a >= 3
a >= 5
a >= 7
满足上列不等式的同时取最小值，当前a = 7时是最小的。

代码

#include
#include
#include

using namespace std;

const int N = 10010, M = 20010;

typedef long long LL;

int q[N];
int h[N], e[M], ne[M], idx;
int dist[N];
int din[N];
int n, m;

void init() {
    memset(h, -1, sizeof h);
    idx = 0;
    memset(din, 0, sizeof din);
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 判断是否有解
bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++)
        if(!din[i])
            q[++tt] = i;
    while(hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(-- din[j] == 0)
                q[++tt] = j;
        }
    }

    return tt == n - 1;
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        init();
        while(m --) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(b, a);
            din[a]++;
        }

        if(!topsort())
            puts("-1");
        else {
        	// 超级源点
            for (int i = 1; i <= n; i ++)
                dist[i] = 888;
			
			// 拓扑图求最长路
            for (int i = 0; i < n; i ++) {
                int j = q[i];
                for (int k = h[j]; ~k; k = ne[k]) {
                    dist[e[k]] = max(dist[e[k]], dist[j] + 1);
                }
            }

            LL ans = 0;
            for (int i = 1; i <= n; i ++) {
                ans += dist[i];
            }

            printf("%lldn", ans);
        }
    }

    return 0;
}

HDU - 3342 Legal or Not 思路

拓扑排序，判断有向图是否存在环问题

代码

#include
#include
#include

using namespace std;

const int N = 110, M = 210;
int h[N], e[M], ne[M], idx;
int q[N];
int din[N];
int n, m;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++) {
        if(!din[i])
            q[++tt] = i;
    }

    while(hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(-- din[j] == 0)
                q[++tt] = j;
        }
    }

    return tt == n - 1;
}

int main() {

    while(~scanf("%d%d", &n, &m) && n) {
        memset(h, -1, sizeof h);
        idx = 0;
        memset(din, 0, sizeof din);

        while(m --) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            din[b]++;
        }

        if(topsort())
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

HDU - 1811 Rank of Tetris 思路

先利用并查集将相等即"="的点进行缩点，即只对一个集合的祖先节点进行操作
跑一遍topsort，若过程中存在两个及以上入度为0的，若不conflict的话那就是uncertain
若拓扑排序入队的点不等于缩点后的数量，说明存在环，及冲突conflict

代码

#include
#include
#include
#include

using namespace std;

const int N = 10010, M = 20010;
int h[N], e[M], ne[M], idx;
int din[N];
int p[N];
int n, m;
int x[M], y[M];
char op[M];
int cnt;
int uflag, cflag;

void init() {
    memset(h, -1, sizeof h);
    memset(din, 0, sizeof din);
    for (int i = 0; i < N; i ++)
        p[i] = i;
    idx = 0; 
    cnt=0;    
    uflag = 0; // 是否不确定
    cflag = 0; // 是否冲突
}

int find(int x) {
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort() {
    queue q;
    for (int i = 0; i < n; i ++) {
        if(!din[i] && p[i] == i)
            cnt++, q.push(i);
    }

    while(q.size()) {
        if(q.size() > 1)
            uflag = 1;
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(-- din[j] == 0) {
                q.push(j);
                cnt++;
            }
        }
    }

    if(cnt != n)
        cflag = 1;
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        init();

        for (int i = 1; i <= m; i ++) {
            cin >> x[i] >> op[i] >> y[i];
            if(op[i] == '=') {
                int px = find(x[i]), py = find(y[i]);
                if(px != py) {
                    cnt ++; // 先统计在同一集合的点的数量,不包括祖先节点, 之后所有祖先节点进行拓扑, 再加上祖先判断cnt是否等于n即可
                    p[px] = py;
                }
            }
        }

        for (int i = 1; i <= m; i ++) {
            if(op[i] == '=')
                continue;
            int px = find(x[i]), py = find(y[i]);
            if(op[i] == '<') {
                add(px, py);
                din[py]++;
            }
            else {
                add(py, px);
                din[px]++;
            }
        }

        topsort();
        if(cflag)
            puts("CONFLICT");
        else if(uflag) puts("UNCERTAIN");
        else
            puts("OK");
    }

    return 0;
}

POJ - 1094 Sorting It All Out 思路

和上题类似。topsort。其他细节在代码中揭晓

代码(参考作者)

    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    const int N = 30;

    int n, m;
    int cnt, kind, d[N], din[N];
    bool st[N];

    void topsort(int x, vector g[]) {
        queue q;
        string res;
        bool flag = true;
        memcpy(d, din, sizeof din);

        for (int i = 0; i < n; i ++)
            if(!d[i])
                q.push(i);
        
        while(q.size()) {
            if(q.size() > 1)
                flag = false;
            int t = q.front();
            q.pop();

            res += 'A' + t;
            vector::iterator it = g[t].begin();
            for (; it != g[t].end(); it ++) {
                if(-- d[*it] == 0)
                    q.push(*it);
            }
        }

        // 若答案长度 == n 并且未出现两个及以上同时入度为0的点
        if(res.length() == n && flag) {
            kind = 1;
            cout << "Sorted sequence determined after " << x << " relations: " << res << ".n";
        }
        // 这种情况, 存在环, 即冲突
        if(res.length() < cnt) {
            kind = 2;
            printf("Inconsistency found after %d relations.n", x);
        }
    }
    int main() {
        while(~scanf("%d%d", &n, &m), n || m) {
            memset(din, 0, sizeof din);
            memset(st, 0, sizeof st);
            cnt = kind = 0;
            // cnt表示当前加的点数量
            vector g[N];

            for (int i = 1; i <= m; i ++) {
                string str;
                cin >> str;
                if(kind)
                    continue;
                int a = str[0] - 'A', b = str[2] - 'A';

                // 标记, 防止重复计算点
                if(!st[a]) {
                    st[a] = true;
                    cnt++;
                }

                if(!st[b]) {
                    st[b] = true;
                    cnt++;
                }

                din[b]++;
                // 加边
                g[a].push_back(b);
                // 每次迭代跑topsort
                topsort(i, g);
            }

            if(!kind)
                puts("Sorted sequence cannot be determined.");
        }

        return 0;
    }

POJ - 2367 Genealogical tree 题意

依次给定1~n的孩子，使每个人的孩子都比那个人后列出。

思路

拓扑排序模板题

代码

#include
#include
#include

using namespace std;

const int N = 110, M = N * N / 2;

int h[N], e[M], ne[M], idx;
int din[N];
int q[N];
int n;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void topsort(){
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++){
        if(!din[i]) q[++ tt] = i;
    }
    
    while(hh <= tt){
        int t = q[hh ++];
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(-- din[j] == 0) q[++ tt] = j;
        }
    }
}

int main(){
    memset(h, -1, sizeof h);
    
    cin >> n;
    
    for(int i = 1; i <= n; i ++){
        int x;
        while(cin >> x, x){
            add(i, x);
            din[x] ++;
        }
    }
    
    topsort();
    
    for(int i = 0; i < n; i ++){
        cout << q[i] << ' ';
    }
    
    return 0;
}

kuangbin专题拓扑排序

C/C++/C#相关栏目本月热门文章