Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iterator>
- #include <unordered_map>
- #include <unordered_set>
- #include <string>
- class Graph {
- private:
- int size_g;
- std::vector<std::vector<int>> data;
- std::vector<int> used;
- public:
- std::vector<bool> isused;
- std::vector<int> colour;
- bool isisdouble = true;
- bool isiscycle = false;
- std::vector<int> cyclepath;
- std::unordered_map<int, int> parents;
- Graph() {
- }
- explicit Graph(int n) {
- data.resize(n);
- isused.resize(n);
- size_g = n;
- std::vector<int> c(n, 0);
- colour = c;
- }
- void insert(int a, int b) {
- if (a != b) {
- data[a - 1].push_back(b);
- }
- }
- void printgraph() {
- for (int i = 0; i < data.size(); i++) {
- for (auto j : data[i]) {
- std::cout << j << " ";
- }
- std::cout << '\n';
- }
- }
- std::vector<int> dfs(int a) {
- std::vector<int> result;
- if (!isused[a - 1]) {
- isused[a - 1] = true;
- result.push_back(a);
- for (int i = 0; i < data[a - 1].size(); i++) {
- if (!isused[data[a - 1][i] - 1]) {
- std::vector<int> preres;
- preres = dfs(data[a - 1][i]);
- result.insert(result.end(), preres.begin(), preres.end());
- }
- }
- }
- return result;
- }
- void colourdfs(int a, int c) {
- if (colour[a - 1] == 0 && isisdouble) {
- colour[a - 1] = c;
- for (int i = 0; i < data[a - 1].size(); i++) {
- if (colour[data[a - 1][i] - 1] == c) {
- isisdouble &= false;
- } else if (colour[data[a - 1][i] - 1] == 0) {
- colourdfs(data[a - 1][i], 3 - c);
- }
- }
- }
- }
- bool isdouble() {
- for (int i = 0; i < size_g; i++) {
- colourdfs(i + 1, 1);
- }
- return isisdouble;
- }
- void cycledfs(int a, int prev) {
- if (!isiscycle) {
- isused[a - 1] = true;
- parents[a] = prev;
- for (int i = 0; i < data[a - 1].size(); i++) {
- if (isused[data[a - 1][i] - 1] && data[a - 1][i] != prev && !isiscycle) {
- isiscycle = true;
- std::vector<int> v;
- int b = a;
- v.push_back(data[a - 1][i]);
- while (b != data[a - 1][i]) {
- v.push_back(b);
- b = parents[b];
- }
- cyclepath = v;
- } else if (!isused[data[a - 1][i] - 1]) {
- cycledfs(data[a - 1][i], a);
- }
- }
- }
- }
- void iscycle() {
- for (int i = 0; i < size_g; i++) {
- if (!isused[i]) {
- std::vector<int> v;
- cycledfs(i + 1, -1);
- }
- }
- if (isiscycle) {
- std::cout << "YES\n";
- std::cout << cyclepath.size() << '\n';
- std::cout << cyclepath[0];
- for (int i = 1; i < cyclepath.size(); i++) {
- std::cout << " " << cyclepath[i];
- }
- } else {
- std::cout << "NO";
- }
- }
- };
- int main() {
- int N, M;
- int a, b;
- std::cin >> N;
- if (N != 0) {
- Graph graph(N);
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- std::cin >> a;
- if (a == 1) {
- graph.insert(i + 1, j + 1);
- }
- }
- }
- graph.iscycle();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement