QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414500#18. Police Stationx-camp0 0ms0kbC++172.7kb2024-05-19 05:01:382024-05-19 05:01:39

Judging History

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

  • [2024-05-19 05:01:39]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-05-19 05:01:38]
  • 提交

answer

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#define MX 11
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];
bool sccVisited[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);
        if (inStack[v])
            low[u] = min(low[u], low[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[sid[u]]) return;
    visited[sid[u]] = true;
    rcnt[sid[u]] = (int) SCCs[sid[u]].size();
    for (auto v: adj[u]) {
        if (sid[v] == sid[u]) continue;
        if (!visited[sid[v]])
            dfs(v);
        if (!sccVisited[sid[v]]) {
            rcnt[sid[u]] += rcnt[sid[v]];
            sccVisited[sid[v]] = true;
        }
    }
}

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);
    }
    set<int> nodes;
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            dfs(i);
            if (rcnt[sid[i]] == N) {
                for (auto x: SCCs[sid[i]])
                    nodes.insert(x);
                break;
            }
        }
    }
    if (nodes.empty())
        cout << 0;
    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

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

951 1923
800 351
371 252
858 700
139 519
10 778
73 554
273 867
745 917
936 933
697 707
825 881
847 732
90 905
720 86
231 352
255 374
943 80
720 81
868 365
595 545
226 655
28 192
50 876
752 852
485 294
814 700
870 491
153 438
111 699
813 673
296 40
426 463
270 168
417 523
391 192
693 344
251 7
660 78...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%