Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int NMAX = 1e5 + 3;
- int n, m;
- vector<int> graph[NMAX];
- enum States {
- UNVIS,
- INSIDE,
- EXITED
- };
- int daddy[NMAX];
- States nstate[NMAX];
- pair<int, int> cycleLim(-1, -1);
- void read() {
- cin >> n >> m;
- assert(n > 0 && n < NMAX);
- for (int i = 0; i < m; i++) {
- int a, b;
- cin >> a >> b;
- assert(a >= 0 && a < n && b >= 0 && b < n);
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- }
- bool dfs(int node, int daddy) {
- nstate[node] = INSIDE;
- for (auto it : graph[node]) {
- if (it == daddy)
- continue;
- if (!nstate[it]) {
- ::daddy[it] = node;
- if (dfs(it, ::daddy[it]))
- return true;
- } else if (nstate[it] == INSIDE) {
- cycleLim = make_pair(it, node);
- return true;
- }
- }
- nstate[node] = EXITED;
- return false;
- }
- void findCycle() {
- fill(daddy, daddy + NMAX, -1);
- fill(nstate, nstate + NMAX, UNVIS);
- for (int i = 0; i < n; i++)
- if (!nstate[i] && dfs(i, daddy[i]))
- break;
- if (cycleLim.first == -1) {
- puts("acyclic");
- return;
- }
- vector<int> cycle = {cycleLim.first};
- for (int i = cycleLim.second; i != cycleLim.first; i = daddy[i])
- cycle.push_back(i);
- cycle.push_back(cycleLim.first);
- reverse(cycle.begin(), cycle.end());
- for (size_t i = 0; i < cycle.size(); i++) {
- cout << cycle[i];
- if (i != cycle.size() - 1)
- cout << "->";
- }//*/
- }
- int main () {
- read();
- findCycle();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement