fork download

copy

#include <bits/stdc++.h>
 
using i64 = long long;
 
void chmin(int &a, int b)
{
    if (a > b)
    {
        a = b;
    }
}
 
void chswap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
 
const int lim = 1e3 + 5;
 
int n, m, timer, scc;
 
std::vector<int> low(lim), d(lim), sz(lim), ssc(lim), in(lim), out(lim), visited(lim);
std::vector<std::vector<int>> adj(lim), node(lim);
std::vector<std::vector<std::array<int, 2>>> adj1(lim);
std::stack<int> st;
bool done[lim];
 
void tarjan(int u)
{
    low[u] = d[u] = ++timer;
 
    st.push(u);
 
    for (int v : adj[u])
    {
        if (done[v] == false)
        {
            if (d[v])
            {
                chmin(low[u], d[v]);
            }
            else
            {
                tarjan(v);
 
                chmin(low[u], low[v]);
            }
        }
    }
 
    if (low[u] == d[u])
    {
        int v;
        ++scc;
        do
        {
            v = st.top();
            st.pop();
 
            done[v] = true;
 
            ssc[v] = scc;
            ++sz[scc];
 
            node[ssc[v]].push_back(v);
        } while (v != u);
    }
}
 
int remove_id;
 
/*
visited:
1 - is visiting
2 - visited
3 - is not visit
*/
 
bool isCycle(int u)
{
    visited[u] = 1;
 
    for (std::array<int, 2> &cur : adj1[u]) if (cur[1] != remove_id)
    {
        int v = cur[0];
 
        if (visited[v] == 1) return true;
 
        if (visited[v] == 0)
        {
            if (isCycle(v))
            {
                return true;
            }
        }
    }
 
    visited[u] = 2;
 
    return false;
}
 
bool will_this_DAG_is_cycle_if_we_remove_edge(int u, int v, int id)
{
    remove_id = id;
    if (ssc[u] == ssc[v])
    {
        for (int i : node[ssc[u]]) visited[i] = 0;
 
        for (int i : node[ssc[u]])
        {
            if (visited[i] == 0)
            {
                if (isCycle(i)) return false;
            }
        }
    }
 
    return true;
}
 
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    std::cin >> n >> m;
 
    std::vector<std::array<int, 2>> edges(m), conditional_edges, ans;
 
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        std::cin >> u >> v;
 
        adj[u].push_back(v);
 
        edges[i] = {u, v};
    }
 
    for (int i = 1; i <= n; ++i)
        if (!d[i])
            tarjan(i);
 
    std::cerr << scc << "\n";
 
    bool has_cycle = false;
    int cycle = 0;
    int strong_components_have_one_cycle = 0;
 
    for (int i = 1; i <= scc; ++i)
    {
        has_cycle = false;
 
        if (sz[i] > 1) has_cycle = true;
        else
        {
            for (int _i = 0; _i < m; ++_i)
            {
                int u = edges[_i][0];
                int v = edges[_i][1];
                if (u == v and ssc[u] == i and ssc[v] == i)
                {
                    has_cycle = true;
                    break;
                }
            }
        }
 
        if (has_cycle)
        {
            ++cycle;
            strong_components_have_one_cycle = i;
        }
    }
 
    if (cycle != 1)
    {
        std::cout << -1 << "\n";
        return 0;
    }
 
    for (int i = 0; i < m; ++i)
    {
        int u = edges[i][0];
        int v = edges[i][1];
 
        if (ssc[u] == strong_components_have_one_cycle and ssc[v] == strong_components_have_one_cycle)
        {
            ++out[u], ++in[v];
 
            adj1[u].push_back({v, i});
            conditional_edges.push_back({u, v});
        }
    }
 
    // std::cout << strong_components_have_one_cycle << "\n";
 
    // std::cout << (int)conditional_edges.size() << "\n";
 
    bool is_simpleCycle = true;
 
    for (int i = 1; i <= n; ++i)
    {
        if (ssc[i] == strong_components_have_one_cycle)
        {
            if (in[i] != 1 || out[i] != 1)
            {
                is_simpleCycle = false;
            }
        }
    }
 
    if (is_simpleCycle)
    {
        std::cerr << "is simple cycle\n";
        ans = conditional_edges;
    }
    else
    {
        std::cerr << "is not simple cycle\n";
        for (int i = 0; i < m; ++i)
        {
            int u = edges[i][0];
            int v = edges[i][1];
 
            if (ssc[u] == strong_components_have_one_cycle and ssc[v] == strong_components_have_one_cycle)
            {
                if (will_this_DAG_is_cycle_if_we_remove_edge(u, v, i))
                {
                    ans.push_back({u, v});
                }
            }
        }
    }
 
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
 
    std::cout << (int)ans.size() << "\n";
 
    for (std::array<int, 2> &edge : ans)
    {
        int u = edge[0];
        int v = edge[1];
 
        std::cout << u << ' ' << v << "\n";
    }
 
    return 0;
 
}
 

Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:5: error: class, interface, or enum expected
void chmin(int &a, int b)
^
Main.java:10: error: class, interface, or enum expected
    }
    ^
Main.java:16: error: class, interface, or enum expected
    a = b;
    ^
Main.java:17: error: class, interface, or enum expected
    b = tmp;
    ^
Main.java:18: error: class, interface, or enum expected
}
^
Main.java:22: error: class, interface, or enum expected
int n, m, timer, scc;
^
Main.java:24: error: class, interface, or enum expected
std::vector<int> low(lim), d(lim), sz(lim), ssc(lim), in(lim), out(lim), visited(lim);
^
Main.java:25: error: class, interface, or enum expected
std::vector<std::vector<int>> adj(lim), node(lim);
^
Main.java:26: error: class, interface, or enum expected
std::vector<std::vector<std::array<int, 2>>> adj1(lim);
^
Main.java:27: error: class, interface, or enum expected
std::stack<int> st;
^
Main.java:28: error: class, interface, or enum expected
bool done[lim];
^
Main.java:30: error: class, interface, or enum expected
void tarjan(int u)
^
Main.java:34: error: class, interface, or enum expected
    st.push(u);
    ^
Main.java:36: error: class, interface, or enum expected
    for (int v : adj[u])
    ^
Main.java:43: error: class, interface, or enum expected
            }
            ^
Main.java:48: error: class, interface, or enum expected
                chmin(low[u], low[v]);
                ^
Main.java:49: error: class, interface, or enum expected
            }
            ^
Main.java:56: error: class, interface, or enum expected
        ++scc;
        ^
Main.java:57: error: class, interface, or enum expected
        do
        ^
Main.java:60: error: class, interface, or enum expected
            st.pop();
            ^
Main.java:62: error: class, interface, or enum expected
            done[v] = true;
            ^
Main.java:64: error: class, interface, or enum expected
            ssc[v] = scc;
            ^
Main.java:65: error: class, interface, or enum expected
            ++sz[scc];
            ^
Main.java:67: error: class, interface, or enum expected
            node[ssc[v]].push_back(v);
            ^
Main.java:68: error: class, interface, or enum expected
        } while (v != u);
        ^
Main.java:69: error: class, interface, or enum expected
    }
    ^
Main.java:81: error: class, interface, or enum expected
bool isCycle(int u)
^
Main.java:85: error: class, interface, or enum expected
    for (std::array<int, 2> &cur : adj1[u]) if (cur[1] != remove_id)
    ^
Main.java:89: error: class, interface, or enum expected
        if (visited[v] == 1) return true;
        ^
Main.java:91: error: class, interface, or enum expected
        if (visited[v] == 0)
        ^
Main.java:96: error: class, interface, or enum expected
            }
            ^
Main.java:102: error: class, interface, or enum expected
    return false;
    ^
Main.java:103: error: class, interface, or enum expected
}
^
Main.java:108: error: class, interface, or enum expected
    if (ssc[u] == ssc[v])
    ^
Main.java:112: error: class, interface, or enum expected
        for (int i : node[ssc[u]])
        ^
Main.java:117: error: class, interface, or enum expected
            }
            ^
Main.java:122: error: class, interface, or enum expected
}
^
Main.java:127: error: class, interface, or enum expected
    std::cin.tie(nullptr);
    ^
Main.java:129: error: class, interface, or enum expected
    std::cin >> n >> m;
    ^
Main.java:131: error: class, interface, or enum expected
    std::vector<std::array<int, 2>> edges(m), conditional_edges, ans;
    ^
Main.java:133: error: class, interface, or enum expected
    for (int i = 0; i < m; ++i)
    ^
Main.java:133: error: class, interface, or enum expected
    for (int i = 0; i < m; ++i)
                    ^
Main.java:133: error: class, interface, or enum expected
    for (int i = 0; i < m; ++i)
                           ^
Main.java:136: error: class, interface, or enum expected
        std::cin >> u >> v;
        ^
Main.java:138: error: class, interface, or enum expected
        adj[u].push_back(v);
        ^
Main.java:140: error: class, interface, or enum expected
        edges[i] = {u, v};
        ^
Main.java:141: error: class, interface, or enum expected
    }
    ^
Main.java:143: error: class, interface, or enum expected
    for (int i = 1; i <= n; ++i)
                    ^
Main.java:143: error: class, interface, or enum expected
    for (int i = 1; i <= n; ++i)
                            ^
Main.java:147: error: class, interface, or enum expected
    std::cerr << scc << "\n";
    ^
Main.java:149: error: class, interface, or enum expected
    bool has_cycle = false;
    ^
Main.java:150: error: class, interface, or enum expected
    int cycle = 0;
    ^
Main.java:151: error: class, interface, or enum expected
    int strong_components_have_one_cycle = 0;
    ^
Main.java:153: error: class, interface, or enum expected
    for (int i = 1; i <= scc; ++i)
    ^
Main.java:153: error: class, interface, or enum expected
    for (int i = 1; i <= scc; ++i)
                    ^
Main.java:153: error: class, interface, or enum expected
    for (int i = 1; i <= scc; ++i)
                              ^
Main.java:157: error: class, interface, or enum expected
        if (sz[i] > 1) has_cycle = true;
        ^
Main.java:158: error: class, interface, or enum expected
        else
        ^
Main.java:160: error: class, interface, or enum expected
            for (int _i = 0; _i < m; ++_i)
                             ^
Main.java:160: error: class, interface, or enum expected
            for (int _i = 0; _i < m; ++_i)
                                     ^
Main.java:163: error: class, interface, or enum expected
                int v = edges[_i][1];
                ^
Main.java:164: error: class, interface, or enum expected
                if (u == v and ssc[u] == i and ssc[v] == i)
                ^
Main.java:167: error: class, interface, or enum expected
                    break;
                    ^
Main.java:168: error: class, interface, or enum expected
                }
                ^
Main.java:175: error: class, interface, or enum expected
            strong_components_have_one_cycle = i;
            ^
Main.java:176: error: class, interface, or enum expected
        }
        ^
Main.java:182: error: class, interface, or enum expected
        return 0;
        ^
Main.java:183: error: class, interface, or enum expected
    }
    ^
Main.java:185: error: class, interface, or enum expected
    for (int i = 0; i < m; ++i)
                    ^
Main.java:185: error: class, interface, or enum expected
    for (int i = 0; i < m; ++i)
                           ^
Main.java:188: error: class, interface, or enum expected
        int v = edges[i][1];
        ^
Main.java:190: error: class, interface, or enum expected
        if (ssc[u] == strong_components_have_one_cycle and ssc[v] == strong_components_have_one_cycle)
        ^
Main.java:194: error: class, interface, or enum expected
            adj1[u].push_back({v, i});
            ^
Main.java:195: error: class, interface, or enum expected
            conditional_edges.push_back({u, v});
            ^
Main.java:196: error: class, interface, or enum expected
        }
        ^
Main.java:205: error: class, interface, or enum expected
    for (int i = 1; i <= n; ++i)
    ^
Main.java:205: error: class, interface, or enum expected
    for (int i = 1; i <= n; ++i)
                    ^
Main.java:205: error: class, interface, or enum expected
    for (int i = 1; i <= n; ++i)
                            ^
Main.java:212: error: class, interface, or enum expected
            }
            ^
Main.java:219: error: class, interface, or enum expected
        ans = conditional_edges;
        ^
Main.java:220: error: class, interface, or enum expected
    }
    ^
Main.java:224: error: class, interface, or enum expected
        for (int i = 0; i < m; ++i)
        ^
Main.java:224: error: class, interface, or enum expected
        for (int i = 0; i < m; ++i)
                        ^
Main.java:224: error: class, interface, or enum expected
        for (int i = 0; i < m; ++i)
                               ^
Main.java:227: error: class, interface, or enum expected
            int v = edges[i][1];
            ^
Main.java:229: error: class, interface, or enum expected
            if (ssc[u] == strong_components_have_one_cycle and ssc[v] == strong_components_have_one_cycle)
            ^
Main.java:234: error: class, interface, or enum expected
                }
                ^
Main.java:240: error: class, interface, or enum expected
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
    ^
Main.java:242: error: class, interface, or enum expected
    std::cout << (int)ans.size() << "\n";
    ^
Main.java:244: error: class, interface, or enum expected
    for (std::array<int, 2> &edge : ans)
    ^
Main.java:247: error: class, interface, or enum expected
        int v = edge[1];
        ^
Main.java:249: error: class, interface, or enum expected
        std::cout << u << ' ' << v << "\n";
        ^
Main.java:250: error: class, interface, or enum expected
    }
    ^
Main.java:254: error: class, interface, or enum expected
}
^
96 errors

Standard output is empty