Cod sursa(job #2972911)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 30 ianuarie 2023 16:56:31
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
using namespace std;
typedef long long ll;
ifstream in("ctc.in");
ofstream out("ctc.out");
ll n,m,i,j,k,l,z,t[200001],w[200001],c[200001],s;vector<int>g[200001],e[200001];bitset<200001>b;
void r(int v)
{
t[v]=w[v]=++z,c[l++]=v,b[v]=1;
for(auto i:g[v])
    if(w[i]==0)
        r(i),bminify(w[v],w[i]);
        else if(b[i])bminify(w[v],t[i]);
if(w[v]==t[v])
{
    do{
        e[s].push_back(c[--l]),b[c[l]]=0;
    }
    while(c[l]!=v);
    ++s;
}
}
int main()
{
//ios_base::sync_with_stdio(false);
//in.tie(nullptr),out.tie(nullptr);
in>>n>>m;
for(k=0;k<m;k++)in>>i>>j,g[i].push_back(j);
for(i=1;i<=n;i++)
    if(t[i]==0)r(i);
cout<<s<<'\n';
for(;s--;cout<<'\n')
    for(auto i:e[s])
        cout<<i<<' ';
}