QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#637537 | #906. 强连通分量 | Bovmelo | WA | 323ms | 58136kb | C++23 | 1.2kb | 2024-10-13 13:15:55 | 2024-10-13 13:15:55 |
Judging History
answer
// Nothing is Given, Everything is Earned.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m; cin >> n >> m;
vector<vector<int>> e(n);
for(int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
e[u].push_back(v);
}
vector<int> dfn(n), low(n), bel(n, -1);
int dfx = 0;
stack<int> st;
vector<vector<int>> scc;
function<void(int, int)> dfs = [&](int u, int fa)
{
dfn[u] = low[u] = ++dfx;
st.push(u);
for(int v : e[u])
{
if(!dfn[v]) dfs(v, u), low[u] = min(low[u], low[v]);
else if(!~bel[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
vector<int> res;
do
{
bel[st.top()] = scc.size();
res.push_back(st.top());
st.pop();
} while(res.back() != u);
scc.push_back(res);
}
};
for(int i = 1; i <= n; i++)
if(!dfn[i]) dfs(i, i);
cout << scc.size() << "\n";
for(auto v : scc | views::reverse)
{
cout << v.size() << " ";
for(int i : v) cout << i << " ";
cout << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 1 5 2 0 3 2 4 1 1 2
result:
ok OK
Test #2:
score: -100
Wrong Answer
time: 323ms
memory: 58136kb
input:
500000 500000 389812 410922 255712 339244 274009 248522 347288 199231 235313 301629 469588 84917 364188 449407 392348 436920 26220 198288 162188 468965 274222 92196 463222 408478 231663 467768 382681 38083 412497 160479 280851 268689 101149 25450 62271 9177 38892 268598 273853 250782 191939 89247 40...
output:
499591 1 500000 1 499999 1 499995 1 499994 1 499989 1 499988 1 499987 1 499983 1 499978 1 499975 1 499972 1 499969 1 499965 1 499964 1 499954 1 499949 1 499947 1 499942 1 499939 1 499932 1 499928 1 499926 1 499925 1 499924 1 499919 1 499918 1 499915 1 499910 1 499909 1 4...
result:
wrong answer Integer 500000 violates the range [0, 499999]