acwing::acwing848_408 命名空间参考

1. 有向图的拓扑序列

更多...

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing848_408, case1)
	TEST (acwing848_408, case2)
	TEST (acwing848_408, case3)
	TEST (acwing848_408, case4)

详细描述

1. 有向图的拓扑序列

函数说明

main()

int acwing::acwing848_408::main	(	istream &	cin,
		ostream &	cout )

在文件 acwing408.cpp 第 846 行定义.

                                              {
            ostringstream oss;
            int n, m;
            cin >> n >> m;
            vector<unordered_set<int>> g = vector<unordered_set<int>>(n + 1, unordered_set<int>());
            vector<short> in             = vector<short>(n + 1, 0);
            while(m--) {
                int x, y;
                cin >> x >> y;
                if(g[x].find(y) != g[x].end())
                    continue;
                g[x].insert(y);
                in[y]++;
            }
            bool flag = true;
            while(flag) {
                for(int i = 1; i <= n; i++) {
                    if(in[i] == 0) {
                        flag = false;
                        oss << i << ' ';
                        for(int j: g[i]) {
                            in[j]--;
                        }
                        in[i] = -1;
                    }
                }
                if(flag) {
                    break;
                }
                flag = true;
            }
            for(int i = 1; i <= n; i++) {
                if(in[i] != -1) {
                    cout << -1;
                    return 0;
                }
            }
            cout << oss.str();
            return 0;
        }

被这些函数引用 TEST(), TEST(), TEST() , 以及 TEST().

TEST() [1/4]

acwing::acwing848_408::TEST	(	acwing848_408	,
		case1	)

在文件 acwing408_test.cpp 第 1204 行定义.

                                   {
            istringstream in("3 3\n"
                             "1 2\n"
                             "2 3\n"
                             "1 3");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("1 2 3 ",
                      ans);
        }

引用了 main().

TEST() [2/4]

acwing::acwing848_408::TEST	(	acwing848_408	,
		case2	)

在文件 acwing408_test.cpp 第 1216 行定义.

                                   {
            istringstream in("5 10\n"
                             "2 3\n"
                             "2 5\n"
                             "2 5\n"
                             "1 4\n"
                             "2 4\n"
                             "1 2\n"
                             "2 3\n"
                             "2 4\n"
                             "3 5\n"
                             "3 4");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("1 2 3 4 5 ",
                      ans);
        }

引用了 main().

TEST() [3/4]

acwing::acwing848_408::TEST	(	acwing848_408	,
		case3	)

在文件 acwing408_test.cpp 第 1235 行定义.

                                   {
            istringstream in("10 20\n"
                             "2 3\n"
                             "5 10\n"
                             "1 5\n"
                             "2 5\n"
                             "4 6\n"
                             "1 2\n"
                             "4 5\n"
                             "3 7\n"
                             "2 10\n"
                             "4 4\n"
                             "1 7\n"
                             "1 2\n"
                             "1 4\n"
                             "3 8\n"
                             "7 8\n"
                             "1 2\n"
                             "2 5\n"
                             "4 7\n"
                             "2 9\n"
                             "3 10");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("-1",
                      ans);
        }

引用了 main().

TEST() [4/4]

acwing::acwing848_408::TEST	(	acwing848_408	,
		case4	)

在文件 acwing408_test.cpp 第 1264 行定义.

                                   {
            istringstream in("4 4\n"
                             "2 1\n"
                             "1 3\n"
                             "1 4\n"
                             "3 4");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("2 1 3 4 ",
                      ans);
        }

引用了 main().