Cod sursa(job #3255400)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 10 noiembrie 2024 15:57:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#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 fto(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 2000003ll
#define nmax 1000006
#define lim 351
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
//typedef tree<int,null_type,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
//functions: x.find_by_order(k), x.order_of_key(t)
using namespace std;
typedef long long ll;
ifstream in("ctc.in");
ofstream out("ctc.out");
//FILE *fin=fopen("infasuratoare.in","r");
//FILE *fout=fopen("infasuratoare.out","w");
ll n,m,i,j,k,l,z,x,c[nmax],e[nmax],on[nmax],oc[nmax];
vector<ll>g[nmax],r[nmax];
void tr(ll v)
{
    e[v]=1,on[v]=oc[v]=++z,c[l++]=v;
    for(auto i:g[v])
        if(on[i]==0)
            tr(i),bminify(oc[v],oc[i]);
            else if(e[i])bminify(oc[v],on[i]);
    if(on[v]==oc[v]){++x;
        do
            {e[c[--l]]=0,r[v].emplace_back(c[l]);}
        while(c[l]!=v);
    }
}
int main()
{
std::ios_base::sync_with_stdio(0);
in>>n>>m;
fto(k,0,m)
    in>>i>>j,g[i].emplace_back(j);
fto(k,1,n+1)if(on[k]==0)tr(k);
//fto(k,1,n+1)cout<<k<<' '<<oc[k]<<'\n';
out<<x;
fto(i,1,n+1)
    if(r[i].size()){
        out<<'\n';
        for(auto j:r[i])out<<j<<' ';
    }
}