Cod sursa(job #2120961)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 3 februarie 2018 10:22:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;
vector <int> g[100003],s,sol[100003];
bitset <100003> viz;
int ix[100003], llk[100003];
int n,m,a,b,index=1,k;
void dfs(int ln)
{
    ix[ln]=index;
    llk[ln]=index;
    s.push_back(ln);
    ++index;
    viz[ln]=1;
    for(int i:g[ln])
    {
        if(!ix[i])
        {
            dfs(i);
            llk[ln]=min(llk[ln],llk[i]);
        }
        else if(viz[i])
            llk[ln]=min(llk[ln],ix[i]);
    }
    if(llk[ln]==ix[ln])
    {
        int w;
        do
        {
            w=s.back();
            s.pop_back();
            sol[k].push_back(w);
            viz[w]=0;
        }
        while(ln!=w);
        ++k;
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d", &n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("\n%d %d", &a,&b);
        g[a].push_back(b);
    }
    for(int i=1;i<=n;++i)
    {
        if(!ix[i])
        {
            dfs(i);
        }
    }
    cout<<k<<"\n";
    for(int i=0;i<k;++i)
    {
        for(int j:sol[i])
            cout<<j<<" ";
        cout<<"\n";
    }
    return 0;
}