QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674284#906. 强连通分量operator_WA 0ms20000kbC++141.4kb2024-10-25 14:56:302024-10-25 14:56:31

Judging History

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

  • [2024-10-25 14:56:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:20000kb
  • [2024-10-25 14:56:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)