| 178 | } |
| 179 | |
| 180 | void test_11() { |
| 181 | vvi adj(10); |
| 182 | |
| 183 | adj[0].push_back(8); |
| 184 | adj[0].push_back(4); |
| 185 | adj[1].push_back(9); |
| 186 | adj[2].push_back(6); |
| 187 | adj[3].push_back(6); |
| 188 | adj[3].push_back(0); |
| 189 | adj[3].push_back(5); |
| 190 | adj[4].push_back(8); |
| 191 | adj[5].push_back(4); |
| 192 | adj[6].push_back(0); |
| 193 | adj[6].push_back(7); |
| 194 | adj[7].push_back(2); |
| 195 | adj[8].push_back(5); |
| 196 | |
| 197 | pair<union_find, vi> res = scc(adj); |
| 198 | union_find scc = res.first; |
| 199 | vi dag = res.second; |
| 200 | |
| 201 | vi num(10); |
| 202 | num[0] = 1; |
| 203 | num[1] = 3; |
| 204 | num[2] = 5; |
| 205 | num[3] = 2; |
| 206 | num[4] = 0; |
| 207 | num[5] = 0; |
| 208 | num[6] = 5; |
| 209 | num[7] = 5; |
| 210 | num[8] = 0; |
| 211 | num[9] = 4; |
| 212 | |
| 213 | for (int i = 0; i < 10; i++) |
| 214 | { |
| 215 | for (int j = 0; j < 10; j++) |
| 216 | { |
| 217 | assert_equal(num[i] == num[j], scc.find(i) == scc.find(j)); |
| 218 | } |
| 219 | } |
| 220 | |
| 221 | vi idx(10); |
| 222 | for (int i = 0; i < size(dag); i++) { |
| 223 | idx[scc.find(dag[i])] = i; |
| 224 | } |
| 225 | |
| 226 | assert_true(idx[scc.find(4)] < idx[scc.find(0)]); |
| 227 | assert_true(idx[scc.find(4)] < idx[scc.find(6)]); |
| 228 | assert_true(idx[scc.find(4)] < idx[scc.find(3)]); |
| 229 | assert_true(idx[scc.find(0)] < idx[scc.find(3)]); |
| 230 | assert_true(idx[scc.find(0)] < idx[scc.find(6)]); |
| 231 | assert_true(idx[scc.find(6)] < idx[scc.find(3)]); |
| 232 | assert_true(idx[scc.find(9)] < idx[scc.find(1)]); |
| 233 | } |
| 234 | |
| 235 | void test_12() { |
| 236 | vvi adj(4); |
no test coverage detected