Cod sursa(job #3315439)

Utilizator popescu_georgePopescu George popescu_george Data 14 octombrie 2025 09:47:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<bitset>
#include<stack>
#include<vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int N=1e5+1,M=2e5;
int k,q[M],r,u[N],v[N],z;
vector<int> g[N];
stack<int> s;
bitset<N> w;
void A(int i)
{
    u[i]=v[i]=++k,s.push(i),w[i]=1;
    for(int j:g[i])
        if(!u[j])
            A(j),v[i]=min(v[i],v[j]);
        else if(w[j])
            v[i]=min(v[i],u[j]);
    if(u[i]==v[i]) {
        for(int j=0;j!=i;j=s.top(),s.pop(),w[j]=0,q[z++]=j);
        ++r,q[z++]=0;
    }
}
int main()
{
    int m,n;
    for(cin>>n>>m;m--;) {
        int i,j;
        cin>>i>>j,g[i].push_back(j);
    }
    for(int i=1;i<=n;++i)
        if(!u[i])
            A(i);
    cout<<r<<'\n';
    for(int i=0;i<z;q[i]?cout<<q[i]<<' ':cout<<'\n',++i);
    return 0;
}