pat::a::a1021 命名空间参考

1021 Deepest Root 更多...

函数
int	dfs (const vector< unordered_set< int > > &g, int father, int nd)
int	dfs (int father, int nd)
int	main (istream &cin, ostream &cout)
	TEST (a1021, case1)
	TEST (a1021, case2)
	TEST (a1021, case3)

详细描述

1021 Deepest Root

函数说明

dfs() [1/2]

int pat::a::a1021::dfs	(	const vector< unordered_set< int > > &	g,
		int	father,
		int	nd )

在文件 pat.cpp 第 5022 行定义.

                                                                             {
                int maximum = 0;
                for(const auto child: g[nd]) {
                    if(child != father) {
                        maximum = max(maximum, dfs(g, nd, child));
                    }
                }
                return maximum + 1;
            }

引用了 dfs().

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

dfs() [2/2]

int pat::a::a1021::dfs	(	int	father,
		int	nd )

main()

int pat::a::a1021::main	(	istream &	cin,
		ostream &	cout )

在文件 pat.cpp 第 5032 行定义.

                                                  {
                int n;
                cin >> n;
                auto g = vector<unordered_set<int>>(n + 1);
                vector deep(n + 1, 0);
                UnionFind uf(n + 1);
                for(int i = 1; i < n; i++) {
                    int a, b;
                    cin >> a >> b;
                    uf.unite(a, b);
                    g[a].insert(b);
                    g[b].insert(a);
                }
                unordered_set<int> us;
                for(int i = 1; i <= n; i++) {
                    us.insert(uf.find(i));
                }
                if(us.size() != 1) {
                    cout << "Error: " << us.size() << " components";
                    return 0;
                }
                int maximum = 0;
                for(int i = 1; i <= n; i++) {
                    deep[i] = dfs(g, 0, i);
                    maximum = max(maximum, deep[i]);
                }
                for(int i = 1; i <= n; i++) {
                    if(deep[i] == maximum) {
                        cout << i << endl;
                    }
                }
                return 0;
            }

引用了 dfs(), UnionFind::find() , 以及 UnionFind::unite().

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

TEST() [1/3]

pat::a::a1021::TEST	(	a1021	,
		case1	)

在文件 pat_test.cpp 第 2259 行定义.

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

引用了 main().

TEST() [2/3]

pat::a::a1021::TEST	(	a1021	,
		case2	)

在文件 pat_test.cpp 第 2273 行定义.

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

引用了 main().

TEST() [3/3]

pat::a::a1021::TEST	(	a1021	,
		case3	)

在文件 pat_test.cpp 第 2284 行定义.

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

引用了 main().