QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#674284 | #906. 强连通分量 | operator_ | WA | 0ms | 20000kb | C++14 | 1.4kb | 2024-10-25 14:56:30 | 2024-10-25 14:56:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int m=0,s=0;char ch=getchar();
while(!isdigit(ch)) m|=(ch=='-'),ch=getchar();
while( isdigit(ch)) s=s*10+ch-'0',ch=getchar();
return m?-s:s;
}
bool MBE;
namespace SOLVER {
int n,m,h[500005],cnt=1,fl[500005],ans;struct Edge {int u,v,nxt;} e[1000005];
void add(int u,int v) {e[++cnt]={u,v,h[u]},h[u]=cnt;}
int dfn[500005],low[500005],tot,num;stack<int> st;vector<int> scc[500005];
void tarjan(int u,int p) {
st.push(u),fl[u]=1,dfn[u]=low[u]=++tot;
for(int i=h[u],v;v=e[i].v;i=e[i].nxt) if((i^p)!=1) {
if(!dfn[v]) tarjan(v,i),low[u]=min(low[u],low[v]);
else if(fl[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
num++;
while(1) {
int v=st.top();fl[v]=0;
scc[num].emplace_back(v);st.pop();if(v==u) break;
}
}
}
void MAIN() {
cin>>n>>m;for(int i=1,u,v;i<=m;i++) u=rd()+1,v=rd()+1,add(u,v),add(v,u);
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
cout<<num<<endl;
for(int i=1;i<=num;i++) {
cout<<scc[i].size()<<' ';
for(int j:scc[i]) printf("%lld ",j-1);
puts("");
}
}
}
bool MED;
signed main() {
//freopen(".in","r",stdin);freopen(".out","w",stdout);
SOLVER::MAIN();
cerr<<(&MED-&MBE)/1024<<"KB "<<clock()*1000/CLOCKS_PER_SEC<<" ms"<<endl;
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 20000kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 1 5 1 2 2 4 1
result:
wrong answer 4 is later than 2, but there is an edge (4, 2)