Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- class Graph {
- private:
- size_t n_vertexes;
- size_t n_edges;
- std::vector<std::vector<size_t>> m_adj_;
- std::vector<std::vector<size_t>> matrix_adj_;
- std::vector<bool> visited;
- // std::vector<size_t> conn_vert;
- std::vector<size_t> vert_colors;
- bool is_dic;
- bool is_cyc;
- bool cycle_finish;
- size_t vert_v;
- public:
- std::vector<size_t> cycle_vertexes;
- Graph(size_t N, size_t M, std::vector<std::vector<size_t>> m_adj) : n_vertexes(N), n_edges(M),
- m_adj_(std::move(m_adj)), visited(n_vertexes,
- false) {
- vert_colors.resize(n_vertexes + 1);
- is_dic = true;
- vert_v = 1000;
- }
- Graph(size_t N, std::vector<std::vector<size_t>> matrix_adj) : n_vertexes(N), matrix_adj_(std::move(matrix_adj)),
- visited(n_vertexes,
- false) {
- vert_colors.resize(n_vertexes);
- is_cyc = false;
- cycle_finish = false;
- vert_v = 10000000;
- }
- void dfs(size_t now = 1) {
- visited[now] = true;
- for (auto neig : m_adj_[now]) {
- if (!visited[neig]) {
- dfs(neig);
- }
- }
- }
- void bipartite_one_comp(size_t vert = 1, size_t color = 1) {
- vert_colors[vert] = color;
- visited[vert] = true;
- for (auto neig : m_adj_[vert]) {
- if (vert_colors[neig] == vert_colors[vert]) {
- is_dic = false;
- return;
- } else if (vert_colors[neig] == 0) {
- bipartite_one_comp(neig, 3 - vert_colors[vert]);
- }
- }
- }
- bool bipartite_all_comp() {
- for (size_t now = 1; now <= n_vertexes; ++now) {
- if (!visited[now]) {
- bipartite_one_comp(now);
- if (!is_dic) {
- return false;
- }
- }
- }
- return true;
- }
- void cycle_one(size_t vert = 0, size_t ancestor = 100000000) {
- vert_colors[vert] = 1;
- visited[vert] = true;
- for (size_t neig = 0; neig < matrix_adj_[vert].size(); ++neig) {
- if (cycle_finish){
- return;
- }
- if (matrix_adj_[vert][neig] == 1) {
- if (vert_colors[neig] == 1 && neig != ancestor) {
- vert_v = neig;
- is_cyc = true;
- break;
- } else if (vert_colors[neig] == 0) {
- cycle_one(neig, vert);
- }
- }
- }
- vert_colors[vert] = 2;
- if (is_cyc && !cycle_finish) {
- if (vert != vert_v) {
- cycle_vertexes.push_back(vert);
- } else if (vert == vert_v) {
- cycle_vertexes.push_back(vert);
- cycle_finish = true;
- }
- }
- }
- bool cycle_all() {
- for (size_t now = 0; now < n_vertexes; ++now) {
- if (!visited[now]) {
- cycle_one(now);
- if (is_cyc) {
- return true;
- }
- }
- }
- return false;
- }
- };
- void
- dfs(size_t now, std::vector<std::vector<size_t>> &m_adj, std::vector<bool> &first_vis,
- std::vector<size_t> &conn_vert) {
- first_vis[now] = true;
- conn_vert.push_back(now);
- for (auto neig : m_adj[now]) {
- if (!first_vis[neig]) {
- dfs(neig, m_adj, first_vis, conn_vert);
- }
- }
- }
- int main() {
- size_t N;
- std::cin >> N;
- std::vector<std::vector<size_t>> matrix_adj(N, std::vector<size_t>(N));
- size_t vert = 0;
- for (size_t i = 0; i < N; ++i) {
- for (size_t j = 0; j < N; ++j) {
- std::cin >> vert;
- matrix_adj[i][j] = vert;
- }
- }
- Graph g(N, matrix_adj);
- g.cycle_all();
- if (!g.cycle_vertexes.empty()) {
- std::cout << "YES\n";
- std::cout << g.cycle_vertexes.size() << "\n";
- for (unsigned long cycle_vertexe : g.cycle_vertexes) {
- std::cout << cycle_vertexe + 1 << " ";
- }
- } else {
- std::cout << "NO";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement