acwing::acwing240 命名空间参考

1. 食物链

更多...

类
struct	UnionFind

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing240, case1)

详细描述

1. 食物链

函数说明

main()

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

在文件 acwing.cpp 第 7031 行定义.

                                              {
            int n;
            int k;
            cin >> n >> k;
            UnionFind uf(n);
            int ans = 0;
            while(k-- != 0) {
                char d;
                int x;
                int y;
                cin >> d >> x >> y;
                if(x > n || y > n) {
                    ans++;
                    continue;
                }
                x--;
                y--;
                const int px = uf.find(x);
                const int py = uf.find(y);
                if(d == '1') {
                    if(px == py) {
                        if((uf.dist[x] - uf.dist[y]) % 3 != 0) {
                            ans++;
                        }
                    } else {
                        uf.parent[px] = py;
                        uf.dist[px]   = uf.dist[y] - uf.dist[x];
                    }
                } else {
                    if(x == y) {
                        ans++;
                        continue;
                    }
                    if(px == py) {
                        if((uf.dist[x] - uf.dist[y] - 1) % 3 != 0) {
                            ans++;
                        }
                    } else {
                        uf.parent[px] = py;
                        uf.dist[px]   = uf.dist[y] - uf.dist[x] + 1;
                    }
                }
            }
            cout << ans;
            return 0;
        }

引用了 acwing::acwing240::UnionFind::dist, acwing::acwing240::UnionFind::find() , 以及 acwing::acwing240::UnionFind::parent.

被这些函数引用 TEST().

TEST()

acwing::acwing240::TEST	(	acwing240	,
		case1
	)

在文件 acwing_test.cpp 第 3292 行定义.

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

引用了 main().