QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#479873#906. 强连通分量liuhangxin#WA 0ms16052kbC++141.3kb2024-07-15 21:27:452024-07-15 21:27:45

Judging History

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

  • [2024-07-15 21:27:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:16052kb
  • [2024-07-15 21:27:45]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
int n,m;
vector<pii>to[N];
int dfn[N],low[N],tot;
int stk[N],cnt;
bool vis[N],instk[N];
vector<vector<int>>tmp;
inline void dfs(int u,int fa)
{
    dfn[u]=low[u]=++tot;
    stk[++cnt]=u;instk[u]=1;
    for(pii t:to[u]){
        int v=t.fi;
        if(t.se==fa)continue;
        if(!dfn[v])
        {
            dfs(v,t.se);
            low[u]=min(low[u],low[v]);
        }
        else if(instk[v])low[u]=min(low[u],dfn[v]);
    }
    // cout<<u<<" "<<dfn[u]<<" "<<low[u]<<endl;
    if(dfn[u]==low[u])
    {
        int x;
        vector<int>res;
        do
        {
            x=stk[cnt--];
            res.push_back(x);
            instk[x]=0;
        }while(x!=u);
        tmp.push_back(res);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        to[a].push_back({b,i});
        to[b].push_back({a,i});
    }
    for(int i=0;i<n;i++)
        if(!dfn[i])
        dfs(i,0);
    printf("%d\n",(int)tmp.size());
    for(vector<int>res:tmp)
    {
        printf("%d ",(int)res.size());
        for(int x:res)printf("%d ",x);
        puts("");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 16052kb

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)