QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412034#906. 强连通分量myeeWA 3ms39088kbC++111.8kb2024-05-15 23:28:382024-05-15 23:28:38

Judging History

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

  • [2024-05-15 23:28:38]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:39088kb
  • [2024-05-15 23:28:38]
  • 提交

answer

// 那就是希望。
// 即便需要取模,也是光明。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
// Your shadow Gets in the way of my light
std::vector<uint>Way[500005],RWay[500005],R[500005],S;
bol G[500005];uint cnt=0;
voi dfs1(uint p)
{
    G[p]=1;for(auto s:RWay[p])if(!G[s])dfs1(s);
    S.push_back(p);
}
voi dfs2(uint p)
{
    G[p]=0,R[cnt].push_back(p);for(auto s:Way[p])if(G[s])dfs2(s);
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint n,m;scanf("%u%u",&n,&m);
    while(m--){uint u,v;scanf("%u%u",&u,&v),Way[u].push_back(v),RWay[v].push_back(u);}
    for(uint i=0;i<n;i++)if(!G[i])dfs1(i);
    while(S.size())
    {
        if(G[S.back()])dfs2(S.back()),cnt++;
        S.pop_back();
    }
    printf("%u\n",cnt);
    for(uint i=0;i<cnt;i++)
    {
        printf("%u",(uint)R[i].size());
        for(auto s:R[i])printf(" %u",s);
        putchar('\n');
    }
    return 0;
}

// 那就是希望。
// 即便需要取模,也是光明。

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 39088kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
1 2
1 5
2 1 4
2 0 3

result:

wrong answer 5 is later than 2, but there is an edge (5, 2)