QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#414507 | #18. Police Station | x-camp | 0 | 0ms | 0kb | C++17 | 2.6kb | 2024-05-19 05:43:52 | 2024-05-19 05:43:52 |
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];
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, set<int> sccadj[]) {
if (visited[u]) return;
visited[u] = true;
rcnt[u] ++ ;
for (auto v: sccadj[u]) {
if (!visited[sid[v]])
dfs(v, sccadj);
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);
}
set<int> nodes;
set<int> sccadj[scnt];
for (int i = 1; i <= N; ++i) {
for (auto x: adj[i])
if (sid[i] != sid[x])
sccadj[sid[i]].insert(sid[x]);
}
for (int i=0; i<scnt; i++) {
if (!visited[i]) {
dfs(i , sccadj);
if (rcnt[i] == scnt)
for (auto x: SCCs[i])
nodes.insert(x);
}
}
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;
}
詳細信息
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%