QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414530#18. Police Stationx-campCompile Error//C++173.0kb2024-05-19 07:25:142024-05-19 07:25:15

Judging History

你现在查看的是最新测评结果

  • [2024-05-19 07:25:15]
  • 评测
  • [2024-05-19 07:25:14]
  • 提交

answer

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#define MX 1000002
using namespace std;
int N,M;    // Number of vertices
vector<int> adj[MX];    // Adjacency list
vector<int> disc;    // Discovery time of each vertex
vector<int> low;    // Lowest discovery time reachable from the vertex
stack<int> st;    // Stack to store the vertices of the current SCC
vector<bool> inStack;    // Boolean array to check if a vertex is in the stack
int cnt;    // Time counter
vector<vector<int>> SCCs;    // List of all SCCs
int sid[MX]; // scc id
int rcnt[MX]; // reach count from each node
int scnt; //scc count
bool visited[MX];
set<int> sccadj[MX];

void scc(int u) {
    // Initialize discovery time and low value
    disc[u] = low[u] = ++cnt;
    st.push(u);
    inStack[u] = true;
    // Go through all vertices adjacent to this
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            scc(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v])
            low[u] = min(low[u], disc[v]);
    }
    if (low[u] == disc[u]) { //found SCC
        vector<int> scc;
        for (int v=st.top();; v=st.top()) {
            st.pop();
            inStack[v] = false;
            scc.push_back(v);
            if (v == u) break;
        }
        SCCs.push_back(scc);
        for (auto x: scc)
            sid[x] = scnt;
        scnt ++;
    }
}
void dfs(int u) {
    if (visited[u]) return;
    visited[u] = true;
    rcnt[u] ++ ;
    for (auto v: sccadj[u]) {
        if (!visited[v])
            dfs(v);
        rcnt[u] += rcnt[v];
    }
}

int main() {
    cin >> N >> M;
    disc.assign(N+1, -1);
    low.assign(N+1, -1);
    inStack.assign(N+1, false);
    for (int i=0; i<M; i++) {
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    
    for (int i = 1; i <= N; ++i) {
        if (disc[i] == -1)
            scc(i);
    }
    for (int i = 1; i <= N; ++i) {
        for (auto x: adj[i])
            if (sid[i] != sid[x])
                sccadj[sid[i]].insert(sid[x]);
    }
    set<int> nodes;
    
    /*
    for (int i=0; i<scnt; i++) {
        if (!visited[i]) {
            dfs(i);
            if (rcnt[i] == scnt) {
                for (auto x: SCCs[i])
                    nodes.insert(x);
                break;
            }
        }
    }*/
    for (int i=0; i<scnt; i++) {
        memset(visited, 0, 4*scnt);
        memset(rcnt, 0, 4*scnt);
            dfs(i);
            if (rcnt[i] == scnt) {
                for (auto x: SCCs[i])
                    nodes.insert(x);
                break;
            }
    }
    
    if (nodes.empty())
        cout << 0 << endl;
    else {
        cout << nodes.size() << endl;
        for (auto x: nodes)
            cout << x << " ";
        cout << endl;
    }
    /*for (auto &s: SCCs) {
        for (auto v: s)
            cout << v << " " ;
        cout << endl;
    }*/
    return 0;
}



Details

answer.code: In function ‘int main()’:
answer.code:94:9: error: ‘memset’ was not declared in this scope
   94 |         memset(visited, 0, 4*scnt);
      |         ^~~~~~
answer.code:6:1: note: ‘memset’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
    5 | #include <set>
  +++ |+#include <cstring>
    6 | #define MX 1000002