CodeForces875C[拓扑排序] Codeforces Round #440 [Div2E/Div1C]

只要保存每相邻两行字符串第一个不同位即可。然后按照第一个不同位上的字符有: " 来自下一行的大于来自上一行的" 构图，跑拓扑排序即可。

当然要判断一下有没有环构成，有环一定是NO(可以思考一下)。

还可以提前判断下一行是不是上一行的前缀，如果是，那么一定是NO。

在拓扑排序的过程中保存答案。

比如说对于 test9 ：

10 10

8 1 1 6 10 2 2 9 7

6 2 7 1 9 5 10

1 5

7 3 6 9 6 3 7 6

10 3 9 10 3 6 7 10 6 9 6

10 4 4 9 8 2 10 3 6 2 9

8 4 8 6 4 6 4 8 6

2 7 5

6 8 6 2 1 9 8

3 10 2 10
可以得到相互关系：2 > 1，5 > 2，3 > 5，9 > 6，4 > 3，8 > 4，7 > 4，8 > 7，10 > 8。

在进行拓扑排序的过程中, 如果发现需要 2>3 这种情况时， 就要给3打上标记 ， 在代码中我使用一个 f[3] 代表 3的实际值， 当3被
标记时， 直接 -2000000，以方便比较。
当然，如果在比较时发现，就算后面的元素加上了标记，依旧大于前面的 (f[v]>f[u])，此时直接No（这也意味着两个元素都被标记了）；

#include <bits/stdc++.h>

using namespace std;

const int N = ;

int n, m, t, tt;

bool mark[N];

vector<int> a[N];

vector<int> b;

vector<int> G[N];

int f[N], in[N];

void out() {

    puts("No");

    exit();

}

void solve() {

    for (int i = ; i <= m; i++) f[i] = i + ;//类似于一个映射函数，方便比较

    for (int i = ; i < n; i++) {

        bool flag = true;

        int len = min(a[i - ].size(), a[i].size());

        for (int j = ; j < len; j++) {

            if (a[i - ][j] != a[i][j]) {

                G[a[i][j]].push_back(a[i - ][j]);

                in[a[i - ][j]]++;

                flag = false;

                break;

            }

        }

        if (flag && a[i - ].size() > a[i].size()) {

            out();//后一个是前一个的前缀

        }

    }

    int cnt = ;

    //拓扑排序开始

    queue<int>q;

    for (int i = ; i <= m; i++) {

        if (in[i] == ) {

            cnt++;

            q.push(i);

        }

    }

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        for (int i = ; i < G[u].size(); i++) {

            int v = G[u][i];

            in[v]--;

            if (f[v] > f[u]) {

                f[v] -= ; //等于加了个标记

                mark[v] = true;

                if (f[v] > f[u]) out(); //如果加了标记以后，还是小，那么NO

                b.push_back(v);

            }

            if (!in[v]) {

                cnt++;

                q.push(v);

            }

        }

    }

    //拓扑排序结束

    if (cnt < m) out(); //判断是不是所有元素的拓扑序都被判定了(判环)

    puts("Yes");

    cout << b.size() << endl;

    for (int i = ; i < b.size(); i++) {

        cout << b[i] << ' ';

    } puts("");

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = ; i < n; i++) {

        scanf("%d", &t);

        for (int j = ; j < t; j++) {

            scanf("%d", &tt);

            a[i].push_back(tt);

        }

    }

    solve();

    return ;

}

巴特西

CodeForces875C[拓扑排序] Codeforces Round #440 [Div2E/Div1C]

最新文章

热门文章